% --------------------------------------------------------------
% tic_game_space.erl
% --------------------------------------------------------------
%
% Copyright (c) Neal Binnendyk 2009, 2010.
%   <nealabq@gmail.com>
%   <http://nealabq.com/>
%
% == GPL License Notice =============================================
% This code is free software: you can redistribute it and/or modify |
% it under the terms of the GNU General Public License as published |
% by the Free Software Foundation, either version 3 of the License, |
% or (at your option) any later version.                            |
%                                                                   |
% This code is distributed in the hope that it will be useful,      |
% but WITHOUT ANY WARRANTY; without even the implied warranty of    |
% MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the     |
% GNU General Public License for more details. See                  |
%   <http://www.gnu.org/licenses/>                                  |
% == END License Notice =============================================
%
% This is an Erlang module to explore the tic-tac-toe game space.
% You can use this to explore the entire tic-tac-toe game space.
% This DOES NOT play tic tac toe.
%
% This lets you reduce the game space by treating all
% reflected and rotated boards as equal.
% Another way to reduce the size of the game space is to
% describe boards using wildcards. If you were designing
% a simple tic-tac-toe playing machine (maybe in hardware)
% you should consider this approach instead of the rotation
% and reflection method of reducing the game space.
% --------------------------------------------------------------

% --------------------------------------------------------------
% Module

-module( tic_game_space ).

-author( "Neal Binnendyk (nealabq)" ).
-copyright( "Copyright (c) Neal Binnendyk, Ixacta Inc, 2009, 2010." ).

-compile( nowarn_unused_function ).

% --------------------------------------------------------------
% Exports
%
%   Usage examples:
%     tic_game_space:report3( ).
%     tic_game_space:report3( summary).
%     tic_game_space:report3( ply_overview).
%     tic_game_space:report3( 5).
%
%   report(
%     Report_instruction,
%     Start_instruction,
%     Filter_instruction_1st_player,
%     Filter_instruction_2nd_player )
%
%     Report_instruction:
%       summary
%       ply_overview
%       Ply_index (integer 0-9)
%
%     Start_instruction:
%       all_init_moves
%       smart_init_moves
%       corner_init_move
%       side_init_move
%       middle_init_move
%
%     Filter_instruction_1st_player:
%     Filter_instruction_2nd_player:
%       all_moves
%       single_move_simple
%       single_move_minimize_boards
%       smart_moves
%       smart_single_move_simple
%       smart_single_move_minimize_boards

-export([
  report/4,
  report0/0, report1/0, report2/0, report3/0, report4/0,
  report5/0, report6/0, report7/0, report8/0, report9/0,
  report0/1, report1/1, report2/1, report3/1, report4/1,
  report5/1, report6/1, report7/1, report8/1, report9/1 ]).


% --------------------------------------------------------------
% Compiler options
% --------------------------------------------------------------
%
%   Invoke these options with preprocessing flags.
%
%   Example - use defaults:
%     c( '/erlang/tic_game_space').
%
%   Example - enable a special rule (these are the same):
%     c( '/erlang/tic_game_space',
%         {d, c_win_pattern_four_sides}).
%
%     c( '/erlang/tic_game_space',
%         {d, c_win_pattern_four_sides, true}).
%
%   Example - disable a normal rule:
%     c( '/erlang/tic_game_space',
%        {d, c_win_pattern_rising_diagonal, false}).
%
%   Example - change a bunch of things:
%     c( '/erlang/tic_game_space',
%         [ {d, c_symmetry_collapse, false},
%           {d, c_win_pattern_all_rows, false},
%           {d, c_win_pattern_upright_Y},
%           {d, c_win_pattern_upside_down_Y},
%           {d, c_win_pattern_nw_bend},
%           {d, c_win_pattern_se_bend}
%         ]).
%
%   Example:
%     erlc
%       -Dc_symmetry_collapse=false
%       -Dc_win_pattern_all_rows=false
%       -Dc_win_pattern_upright_Y=true
%       -Dc_win_pattern_nw_bend
%       tic_game_space.erl

% --------------------------------------------------------------
% c_symmetry_collapse - default true
%
%   If true, this reduces the game space by treating all
%   reflected and rotated boards as equal.
%
%   This only collapses 8-fold symmetry, although there are
%   many other kinds of symmetries.
%
%   Examples of 2-fold symmetric operations:
%     x-axis reflection
%     rising-diagonal-axis reflection
%     180 degree rotation
%
%   Examples of 4-fold symmetric operations:
%     Combo of x- and y-axis reflections
%     Combo of reflections around both diagonals
%     90 degree rotation

-ifndef( c_symmetry_collapse ).
- define( c_symmetry_collapse, true).
-endif.

% --------------------------------------------------------------
% c_win_pattern_all_rows
% c_win_pattern_all_columns
% c_win_pattern_rising_diagonal
% c_win_pattern_falling_diagonal
%
%   Normal rules: 3 in-a-row
%   All of these default true
%
%   In normal rules you win with 3 in-a-row. Or 3 in-a-column,
%   or 3 in a diagonal.

-ifndef( c_win_pattern_all_rows ).
- define( c_win_pattern_all_rows        , true).
-endif.

-ifndef( c_win_pattern_all_columns ).
- define( c_win_pattern_all_columns     , true).
-endif.

-ifndef( c_win_pattern_rising_diagonal ).
- define( c_win_pattern_rising_diagonal , true).
-endif.

-ifndef( c_win_pattern_falling_diagonal ).
- define( c_win_pattern_falling_diagonal, true).
-endif.

% --------------------------------------------------------------
% c_win_pattern_upright_Y
% c_win_pattern_tilt_right_Y
% c_win_pattern_upside_down_Y
% c_win_pattern_tilt_left_Y
%
%   Special rules: Y patterns
%   All default false
%
%   These rules change the game space dramatically.

-ifndef( c_win_pattern_upright_Y ).
- define( c_win_pattern_upright_Y    , false).
-endif.

-ifndef( c_win_pattern_tilt_right_Y ).
- define( c_win_pattern_tilt_right_Y , false).
-endif.

-ifndef( c_win_pattern_upside_down_Y ).
- define( c_win_pattern_upside_down_Y, false).
-endif.

-ifndef( c_win_pattern_tilt_left_Y ).
- define( c_win_pattern_tilt_left_Y  , false).
-endif.

% --------------------------------------------------------------
% c_win_pattern_upright_4Y
% c_win_pattern_tilt_right_4Y
% c_win_pattern_upside_down_4Y
% c_win_pattern_tilt_left_4Y
%
%   Special rules: 4Y patterns
%   All default false

-ifndef( c_win_pattern_upright_4Y ).
- define( c_win_pattern_upright_4Y    , false).
-endif.

-ifndef( c_win_pattern_tilt_right_4Y ).
- define( c_win_pattern_tilt_right_4Y , false).
-endif.

-ifndef( c_win_pattern_upside_down_4Y ).
- define( c_win_pattern_upside_down_4Y, false).
-endif.

-ifndef( c_win_pattern_tilt_left_4Y ).
- define( c_win_pattern_tilt_left_4Y  , false).
-endif.

% --------------------------------------------------------------
% c_win_pattern_four_corners
% c_win_pattern_four_sides
%
%   Special rules: 4-mark patterns
%   All default false

-ifndef( c_win_pattern_four_corners ).
- define( c_win_pattern_four_corners, false).
-endif.

-ifndef( c_win_pattern_four_sides ).
- define( c_win_pattern_four_sides  , false).
-endif.

% --------------------------------------------------------------
% c_win_pattern_nw_bend
% c_win_pattern_ne_bend
% c_win_pattern_sw_bend
% c_win_pattern_se_bend
%
%   Special rules: corner bends
%   All default false

-ifndef( c_win_pattern_nw_bend ).
- define( c_win_pattern_nw_bend, false).
-endif.

-ifndef( c_win_pattern_ne_bend ).
- define( c_win_pattern_ne_bend, false).
-endif.

-ifndef( c_win_pattern_sw_bend ).
- define( c_win_pattern_sw_bend, false).
-endif.

-ifndef( c_win_pattern_se_bend ).
- define( c_win_pattern_se_bend, false).
-endif.

% --------------------------------------------------------------
% c_patterns_have_symmetry
%
%   True if all winning patterns have 8-fold symmetry.
%   ?c_symmetry_collapse should only be true if
%   ?c_patterns_have_symmetry is also true. Otherwise reported
%   results are not accurate.

-define( c_patterns_have_symmetry,
   ( (?c_win_pattern_rising_diagonal =:=
      ?c_win_pattern_falling_diagonal)
       andalso

     (?c_win_pattern_upright_Y =:= ?c_win_pattern_tilt_right_Y )
       andalso
     (?c_win_pattern_upright_Y =:= ?c_win_pattern_upside_down_Y)
       andalso
     (?c_win_pattern_upright_Y =:= ?c_win_pattern_tilt_left_Y  )
       andalso

     (?c_win_pattern_upright_4Y =:=
      ?c_win_pattern_tilt_right_4Y )
       andalso
     (?c_win_pattern_upright_4Y =:=
      ?c_win_pattern_upside_down_4Y)
       andalso
     (?c_win_pattern_upright_4Y =:=
      ?c_win_pattern_tilt_left_4Y  )
       andalso

     (?c_win_pattern_nw_bend =:= ?c_win_pattern_ne_bend) andalso
     (?c_win_pattern_nw_bend =:= ?c_win_pattern_sw_bend) andalso
     (?c_win_pattern_nw_bend =:= ?c_win_pattern_se_bend) )
   ).


% --------------------------------------------------------------
% Exported reporting functions
% --------------------------------------------------------------
%
%   Here are a few reporting functions for describing parts of
%   the tic-tac-toe game space. You can use these as a starting
%   place for writing your own reports.
%
%   These are meant to provide an overview of the tic-tac-toe
%   game space, and also let you examine boards in the space.
%
%   These functions take zero or one argument. When called with
%   no arguments these functions report on general facts about
%   a game space. An arguement (interpreted as a ply_index)
%   changes it so the report is about the boards in a ply.
%
%     report6( )  - reports on game space 6
%     report6( 5) - report on the boards at ply 5, game space 6
%
%   Improvements?
%     Generate code (in C? Javascript?) to match boards and play
%     the game of tic-tac-toe.
%
%     Generate HTML tables for its reports.
%     Generate XML.
%
%     Put everything under one function. It asks for user input,
%     you specify what kind of game space you want and what
%     report you want and how you want to present the report.
%
%     A graphics user interface.
%     A web interface.
%       Start by letting the user choose options.
%       The first option is "Do you want to treat all board
%       reflections and rotations as equal?"
%
%       Starting with the full game space, let the user filter
%       out moves. For example you might want to filter out all
%       dumb moves in ply 5.
%       The user can keep filtering out moves to carve out any
%       game space.
%
%       Let the user craft patterns (wildcards) to simplify the
%       logic behind move choices.
%
%       If we're exploring another game (not tic-tac-toe) with
%       a large game space, we could let the user evaluate
%       specific moves and plys to see where they lead.
%       The code does not have to generate an entire game space.
%       We only do that because this game space is small.
%
%     Bigger boards? More dimensions?
%     Other turn-based games?
%     Other turn-based simulations. Like a sim or a life game.

% --------------------------------------------------------------
% report(
%     Report_instruction,
%     Start_instruction,
%     Filter_instruction_1st_player,
%     Filter_instruction_2nd_player )
%
%   Report_instruction:
%     summary
%     ply_overview
%     Ply_index (integer 0-9)
%
%   Start_instruction:
%     all_init_moves
%     smart_init_moves
%     corner_init_move
%     side_init_move
%     middle_init_move
%   Start_instruction is a filter instruction for player 1,
%   but only for the first move.
%
%   Filter_instruction_1st_player:
%   Filter_instruction_2nd_player:
%     all_moves
%     single_move_simple
%     single_move_minimize_boards
%     smart_moves
%     smart_single_move_simple
%     smart_single_move_minimize_boards
%   This instruction does not apply to the first move by the
%   1st player.

report(
    Report_instruction,
    Start_instruction,
    Filter_instruction_1st_player,
    Filter_instruction_2nd_player )
->
  write_line( "Tic-tac-toe game space:"),

  write_string( "  First moves (player 1): "),
  write_line(
    case Start_instruction of
      all_init_moves   -> "All moves (no filter)";
      smart_init_moves -> "Smart init moves only";
      corner_init_move -> "Corner only (1 move)";
      side_init_move   -> "Side only (1 move)";
      middle_init_move -> "Middle only (1 move)"
    end),

  write_string( "  Player 1 move filter: "),
  write_line(
    case Filter_instruction_1st_player of
      all_moves   -> "All moves (no filter)";
      smart_moves -> "Smart moves only";
      single_move_simple ->
        "1 move, chosen arbitrarily";
      smart_single_move_simple ->
        "1 smart move, chosen arbitrarily";
      single_move_minimize_boards ->
        "1 move, minimize boards in next ply";
      smart_single_move_minimize_boards ->
        "1 smart move, minimize boards next ply"
    end),

  write_string( "  Player 2 move filter: "),
  write_line(
    case Filter_instruction_2nd_player of
      all_moves   -> "All moves (no filter)";
      smart_moves -> "Smart moves only";
      single_move_simple ->
        "1 move, chosen arbitrarily";
      smart_single_move_simple ->
        "1 smart move, chosen arbitrarily";
      single_move_minimize_boards ->
        "1 move, minimize boards in next ply";
      smart_single_move_minimize_boards ->
        "1 smart move, minimize boards next ply"
    end),

  report_game_space(
    Report_instruction,
    filter_game_space(
      Start_instruction,
      Filter_instruction_1st_player,
      Filter_instruction_2nd_player,
      full_game_space( ))).

% --------------------------------------------------------------
% Report on the full tic-tac-toe game space.
%
%   The full game space encompasses every possible tic-tac-toe
%   game, even ones with very perverse sequences of moves. The
%   moves just have to be legal, with player 1 and player 2
%   taking turns. Games do not continue after a player wins with
%   3 in-a-row.
%
%   Usage:
%     report0( )              same as report0( summary)
%     report0( summary)       report summary of game space
%     report0( ply_overview)  describe each of the plys
%     report0( Ply_index)     describe the boards in one ply
%                               Ply_index is integer 0-9
%
%   Game space:
%     Player 1: all moves
%     Player 2: all moves

report0( ) -> report0( summary ).
report0( Instruction ) ->
  write_line( "Full tic-tac-toe game space:"),
  write_line( "  Player 1: all moves"),
  write_line( "  Player 2: all moves"),
  Full_game_space = full_game_space( ),
  report_game_space( Instruction, Full_game_space).

% --------------------------------------------------------------
% Report on the game space where neither player makes mistakes.
%
%   This is a subset of the full game space.
%   This is the intersection of the "smart 1st player" and
%   "smart 2nd player" game spaces described below.
%
%   This shows the part of the tic-tac-toe game space that you'd
%   normally see, assuming you and the other player know how to
%   avoid losing. All game paths lead to tie games.
%
%   This does not show all possible tie games. It is possible to
%   make a mistake and let the other player get into a winning
%   situation, and then for the other player to also make a
%   mistake so you can get back to a tie.
%
%   Instruction values:
%     summary
%     ply_overview
%     Ply_index 0-9
%
%   Game space:
%     Player 1: all smart moves
%     Player 2: all smart moves

report1( ) -> report1( summary ).
report1( Instruction ) ->
  write_line( "Smart tic-tac-toe game space:"),
  write_line( "  Player 1: all smart moves"),
  write_line( "  Player 2: all smart moves"),
  report_game_space( Instruction, smart_game_space( )).

% --------------------------------------------------------------
% Report on game space where the 1st player never makes a
% mistake.
%
%   This is a subset of the full game space, and a superset of
%   of the "smart game space" where neither player makes any
%   mistakes.
%
%   Player 1 never loses in this game space.
%
%   In this game space player 1 is restricted to only non-dumb
%   moves, but player 2 is not restricted. All possible moves
%   for player 2 are represented. If you were building a machine
%   to play against a human, and the machine always got the
%   first move, then you could use this game space to describe
%   all moves you might want to allow your machine to make.
%   (Unless you wanted your machine to lose occasionally).
%
%   Instruction values:
%     summary
%     ply_overview
%     Ply_index 0-9
%
%   Game space:
%     Player 1: all smart moves
%     Player 2: all moves

report2( ) -> report2( summary ).
report2( Instruction ) ->
  write_line( "Smart 1st player game space:"),
  write_line( "  Player 1: all smart moves"),
  write_line( "  Player 2: all moves"),
  report_game_space(
    Instruction,
    smart_game_space_1st_player(
      all_init_moves, smart_moves, full_game_space( ))).

% --------------------------------------------------------------
% Report on game space where the 2nd player never makes a
% mistake.
%
%   Player 2 (who does not move first) never loses in this game
%   space (under normal rules).
%
%   All possible moves by player 1 are captured.
%
%   Instruction values:
%     summary
%     ply_overview
%     Ply_index 0-9
%
%   Game space:
%     Player 1: all moves
%     Player 2: all smart moves

report3( ) -> report3( summary ).
report3( Instruction ) ->
  write_line( "Smart 2nd player game space:"),
  write_line( "  Player 1: all moves"),
  write_line( "  Player 2: all smart moves"),
  report_game_space(
    Instruction,
    smart_game_space_2nd_player(
      all_init_moves, smart_moves, full_game_space( ))).

% --------------------------------------------------------------
% Report on a subset of the game space where the 1st player
% never makes a mistake.
%
%   In this game space, the 1st player starts with an X in the
%   corner. All other moves by the player 1 are also chosen
%   ahead of time.
%
%   The algorithm that chooses moves ahead of time is simple.
%   If there are several moves available, the first one grabbed
%   is the move that's chosen. There is no further analysis.
%
%   All possible moves (responses) by player 2 are captured.
%
%   Instruction values:
%     summary
%     ply_overview
%     Ply_index 0-9
%
%   Game space:
%     Player 2: all moves
%     Player 1: single smart move
%       1st move: Corner
%       Algorithm for chosing other moves: Simple

report4( ) -> report4( summary ).
report4( Instruction ) ->
  write_line( "Smart 1st player, moves picked ahead of time:"),
  write_line( "  Player 2: all moves"),
  write_line( "  Player 1:"),
  write_line( "    First move : corner"),
  write_line( "    Move choice: simple"),
  report_game_space(
    Instruction,
    smart_game_space_1st_player(
      corner_init_move,
      smart_single_move_simple,
      full_game_space( ))).

% --------------------------------------------------------------
% Report on a subset of the game space where the 1st player
% never makes a mistake.
%
%   In this game space, the 1st player starts with an X in the
%   corner. All other moves by the player 1 are also chosen
%   ahead of time.
%
%   The algorithm that chooses moves ahead of time is
%   complicated and tries to minimize the number of boards
%   in the game space.
%
%   All possible moves (responses) by player 2 are captured.
%
%   Instruction values:
%     summary
%     ply_overview
%     Ply_index 0-9
%
%   Game space:
%     Player 2: all moves
%     Player 1: single smart move
%       1st move: Corner
%       Algorithm for chosing other moves: Minimize Boards

report5( ) -> report5( summary ).
report5( Instruction ) ->
  write_line( "Smart 1st player, moves picked ahead of time:"),
  write_line( "  Player 2: all moves"),
  write_line( "  Player 1:"),
  write_line( "    First move : corner"),
  write_line( "    Move choice: minimize boards"),
  report_game_space(
    Instruction,
    smart_game_space_1st_player(
      corner_init_move,
      smart_single_move_minimize_boards,
      full_game_space( ))).

% --------------------------------------------------------------
% Report on a subset of the game space where the 1st player
% never makes a mistake.
%
%   In this game space, the 1st player starts with an X in the
%   side. All other moves by the player 1 are also chosen
%   ahead of time.
%
%   The algorithm that chooses moves ahead of time is
%   complicated and tries to minimize the number of boards
%   in the game space.
%
%   All possible moves (responses) by player 2 are captured.
%
%   Instruction values:
%     summary
%     ply_overview
%     Ply_index 0-9
%
%   Game space:
%     Player 2: all moves
%     Player 1: single smart move
%       1st move: Side
%       Algorithm for chosing other moves: Minimize Boards

report6( ) -> report6( summary ).
report6( Instruction ) ->
  write_line( "Smart 1st player, moves picked ahead of time:"),
  write_line( "  Player 2: all moves"),
  write_line( "  Player 1:"),
  write_line( "    First move : side"),
  write_line( "    Move choice: minimize boards"),
  report_game_space(
    Instruction,
    smart_game_space_1st_player(
      side_init_move,
      smart_single_move_minimize_boards,
      full_game_space( ))).

% --------------------------------------------------------------
% Report on a subset of the game space where the 1st player
% never makes a mistake.
%
%   Instruction values:
%     summary
%     ply_overview
%     Ply_index 0-9
%
%   Game space:
%     Player 2: all moves
%     Player 1: single smart move
%       1st move: Middle
%       Algorithm for chosing other moves: Minimize Boards

report7( ) -> report7( summary ).
report7( Instruction ) ->
  write_line( "Smart 1st player, moves picked ahead of time:"),
  write_line( "  Player 2: all moves"),
  write_line( "  Player 1:"),
  write_line( "    First move : middle"),
  write_line( "    Move choice: minimize boards"),
  report_game_space(
    Instruction,
    smart_game_space_1st_player(
      middle_init_move,
      smart_single_move_minimize_boards,
      full_game_space( ))).

% --------------------------------------------------------------
% Report on a subset of the game space where the 2nd player
% never makes a mistake.
%
%   Instruction values:
%     summary
%     ply_overview
%     Ply_index 0-9
%
%   Game space:
%     Player 1: all moves
%     Player 2: single smart move
%       Algorithm for chosing other moves: Simple
%
%   When trimming the moves for player 1 we specify a starting
%   move (corner, side, or middle). But that's not relevant in
%   this case since the 2nd player has to have a response to
%   all of the first moves.

report8( ) -> report8( summary ).
report8( Instruction ) ->
  write_line( "Smart 2nd player, moves picked ahead of time:"),
  write_line( "  Player 1: all moves"),
  write_line( "  Player 2: single move for every situation"),
  write_line( "    Move choice: smart, simple"),
  report_game_space(
    Instruction,
    smart_game_space_2nd_player(
      all_init_moves,
      smart_single_move_simple,
      full_game_space( ))).

% --------------------------------------------------------------
% Report on a subset of the game space where the 2nd player
% never makes a mistake.
%
%   Instruction values:
%     summary
%     ply_overview
%     Ply_index 0-9
%
%   Game space:
%     Player 1: all moves
%     Player 2: single smart move
%       Algorithm for chosing other moves: Minimize Boards

report9( ) -> report9( summary ).
report9( Instruction ) ->
  write_line( "Smart 2nd player, moves picked ahead of time:"),
  write_line( "  Player 1: all moves"),
  write_line( "  Player 2: single move for every situation"),
  write_line( "    Move choice: smart, minimize boards"),
  report_game_space(
    Instruction,
    smart_game_space_2nd_player(
      all_init_moves,
      smart_single_move_minimize_boards,
      full_game_space( ))).


% --------------------------------------------------------------
% Game space reporting details
% --------------------------------------------------------------
%
%   There are several things we can count:
%     Games (paths thru the game space)
%     Boards
%     Moves (transitions between boards)

% --------------------------------------------------------------
% report_game_space( Instruction, Game_space )
%
%   Instruction values:
%     summary
%     ply_overview
%     Ply_index 0-9
%
%   Improvement?
%     Often we want a report on an adjacent pair of plys.
%     Sometimes we just want a report on all the ply pairs
%     affected by one player. For example, the 1st player
%     drives these ply transitions:
%       Pl0 -> Ply1
%       Pl2 -> Ply3
%       Pl4 -> Ply5
%       Pl6 -> Ply7
%       Pl8 -> Ply9

report_game_space( Instruction, Game_space ) ->
  write_special_rules_message( ),
  if
    is_integer( Instruction),
    0 =< Instruction,
    9 >= Instruction ->
      Ply_index = Instruction,
      Ply = lists:nth( Ply_index + 1, Game_space),
      report_ply_boards( Ply);
    Instruction =:= ply_overview ->
      report_game_space_ply_overview( Game_space);
    Instruction =:= summary ->
      report_game_space_summary( Game_space)
  end.

% --------------------------------------------------------------
% write_special_rules_message( )
%
%   Briefly describes any special rules we may be using.
%   Does nothing if we are not using any special rules.

write_special_rules_message( ) ->
  Write_ =
    fun
      ( false, _ ) -> ok;
      ( true, Message ) ->
        write_space( 4),
        write_line( Message)
    end,

  write_line(
    case ?c_symmetry_collapse of
      true  ->
        "  Reduced game space -- 8-fold symmetry collapse";
      false ->
        "  Large game space -- no symmetry collapse"
    end),

  % Use 'case' instead of 'if' here to avoid compiler warnings.
  case
     not ?c_win_pattern_all_rows         orelse
     not ?c_win_pattern_all_columns      orelse
     not ?c_win_pattern_rising_diagonal  orelse
     not ?c_win_pattern_falling_diagonal orelse

         ?c_win_pattern_upright_Y        orelse
         ?c_win_pattern_tilt_right_Y     orelse
         ?c_win_pattern_upside_down_Y    orelse
         ?c_win_pattern_tilt_left_Y      orelse

         ?c_win_pattern_upright_4Y       orelse
         ?c_win_pattern_tilt_right_4Y    orelse
         ?c_win_pattern_upside_down_4Y   orelse
         ?c_win_pattern_tilt_left_4Y     orelse

         ?c_win_pattern_four_corners     orelse
         ?c_win_pattern_four_sides       orelse

         ?c_win_pattern_nw_bend          orelse
         ?c_win_pattern_ne_bend          orelse
         ?c_win_pattern_sw_bend          orelse
         ?c_win_pattern_se_bend
  of
    false -> ok;
    true  ->
      write_line( ),
      write_line( "  Playing with special rules:"),

      Write_( not ?c_win_pattern_all_rows   , "No row wins"   ),
      Write_( not ?c_win_pattern_all_columns, "No column wins"),
      Write_( not ?c_win_pattern_rising_diagonal,
        "No rising diagonal win"),
      Write_( not ?c_win_pattern_falling_diagonal,
        "No falling diagonal win"),

      Write_( ?c_win_pattern_upright_Y     , "V (Y) wins"),
      Write_( ?c_win_pattern_tilt_right_Y  , "< wins"),
      Write_( ?c_win_pattern_upside_down_Y , "^ wins"),
      Write_( ?c_win_pattern_tilt_left_Y   , "> wins"),

      Write_( ?c_win_pattern_upright_4Y    , "4V (Y) wins"),
      Write_( ?c_win_pattern_tilt_right_4Y , "4< wins"),
      Write_( ?c_win_pattern_upside_down_4Y, "4^ wins"),
      Write_( ?c_win_pattern_tilt_left_4Y  , "4> wins"),

      Write_( ?c_win_pattern_four_corners  , "4 corners wins"),
      Write_( ?c_win_pattern_four_sides    , "4 sides wins"),

      Write_( ?c_win_pattern_nw_bend, "NW bend wins"),
      Write_( ?c_win_pattern_ne_bend, "NE bend wins"),
      Write_( ?c_win_pattern_sw_bend, "SW bend wins"),
      Write_( ?c_win_pattern_se_bend, "SE bend wins"),

      write_space( 4),
      write_line(
        case ?c_patterns_have_symmetry of
          true  -> "Winning patterns are symmetric";
          false -> "Winning patterns are not symmetric"
        end),

      case
        ?c_symmetry_collapse and not ?c_patterns_have_symmetry
      of
        false -> ok;
        true ->
          write_space( 4),
          write_line(
            "Warning: Collapsing game space with"
            " non-symmetric patterns!")
      end
  end.

% --------------------------------------------------------------
% report_game_space_summary( Game_space )

report_game_space_summary( Game_space ) ->
  write_line( ),

  % Report total number of game paths in game space.
  write_line( "  Total number of game paths: ~w",
    get_ply_leaf_count( hd( Game_space))),

  % Report total number of boards in game space.
  % Break down the board count as
  %   Number of tie boards
  %   Number of boards where player1 wins
  %   Number where player2 wins
  %   Number of boards player 1 must respond to
  %   Number player 2 must respond to
  write_line( ),
  write_line( "  Total number of boards: ~w",
    get_game_space_board_count( Game_space)),
  write_line( "    Player 1 winning boards : ~w",
    get_game_space_board_count_won_by_1st_player(
      Game_space)),
  write_line( "    Player 2 winning boards : ~w",
    get_game_space_board_count_won_by_2nd_player(
      Game_space)),
  write_line( "    Player 1 must respond to: ~w",
    get_game_space_board_count_requires_1st_player_response(
      Game_space)),
  write_line( "    Player 2 must respond to: ~w",
    get_game_space_board_count_requires_2nd_player_response(
      Game_space)),
  write_line( "    Tie boards              : ~w",
    get_game_space_tie_board_count( Game_space)),

  % Break down the total number of boards again, this time as
  %   Initial board (always 1)
  %   Number of boards produced by player 1
  %   Number of boards produced by player 2
  write_line( ),
  write_line(
    "  Total number of boards can also be broken down as:"),
  write_line( "    Initial board count        : 1"),
  write_line( "    Boards produced by player 1: ~w",
    get_game_space_board_count_produced_by_player_1(
      Game_space)),
  write_line( "    Boards produced by player 2: ~w",
    get_game_space_board_count_produced_by_player_2(
      Game_space)),
  write_line( ).

% --------------------------------------------------------------
% report_game_space_ply_overview( Game_space )
%
%   Report details for all the plys except ply-0.
%   Ply-0 is not very interesting since it only contains the
%   initial blank board. The only interesting statistic, number
%   of game paths in this game space, we've already reported
%   in the summary.

report_game_space_ply_overview( Game_space ) ->
  write_line( ),
  lists:foreach( fun report_ply/1, tl( Game_space)).

% --------------------------------------------------------------
% get_game_space_board_count( Game_space )
%
%   All of the boards in the entire game space, including the
%   initial blank board in ply-0.

get_game_space_board_count( Game_space ) ->
  lists:sum( lists:map( fun get_ply_board_count/1, Game_space)).

% --------------------------------------------------------------
% get_game_space_continuing_board_count( Game_space )
% get_game_space_win_board_count( Game_space )
% get_game_space_tie_board_count( Game_space )
%
%   All the boards in the game space can be divided into these
%   catagories:
%
%     Continuing boards (require a response from player 1 or 2)
%     Won boards (won by either player 1 or 2)
%     Tied boards (last ply only)

get_game_space_continuing_board_count( Game_space ) ->
  lists:sum(
    lists:map(
      fun( Ply ) -> get_ply_state_count( continuing, Ply) end,
      Game_space)).

get_game_space_win_board_count( Game_space ) ->
  lists:sum(
    lists:map(
      fun( Ply ) -> get_ply_state_count( win, Ply) end,
      Game_space)).

get_game_space_tie_board_count( Game_space ) ->
  get_ply_state_count( tie, lists:last( Game_space)).

% --------------------------------------------------------------
% get_game_space_board_count_requires_1st_player_response( G_s )
% get_game_space_board_count_won_by_1st_player( Game_space )
% get_game_space_board_count_requires_2nd_player_response( G_s )
% get_game_space_board_count_won_by_2nd_player( Game_space )
%
%   You can also divide all the boards in the game space into
%   these catagories. This is a finer division than the one
%   above.
%
%     Requires 1st player response
%     Requires 2nd player response
%     Won by 1st player
%     Won by 2nd player
%     Tied boards (last ply only)

get_game_space_board_count_requires_1st_player_response(
    [Ply0, _, Ply2, _, Ply4, _, Ply6, _, Ply8, _] )
->
  get_ply_state_count( continuing, Ply0) +
  get_ply_state_count( continuing, Ply2) +
  get_ply_state_count( continuing, Ply4) +
  get_ply_state_count( continuing, Ply6) +
  get_ply_state_count( continuing, Ply8).

get_game_space_board_count_won_by_1st_player(
    [_, _, _, _, _, Ply5, _, Ply7, _, Ply9] )
->
  get_ply_state_count( win, Ply5) +
  get_ply_state_count( win, Ply7) +
  get_ply_state_count( win, Ply9).

get_game_space_board_count_requires_2nd_player_response(
    [_, Ply1, _, Ply3, _, Ply5, _, Ply7, _, _] )
->
  get_ply_state_count( continuing, Ply1) +
  get_ply_state_count( continuing, Ply3) +
  get_ply_state_count( continuing, Ply5) +
  get_ply_state_count( continuing, Ply7).

get_game_space_board_count_won_by_2nd_player(
    [_, _, _, _, _, _, Ply6, _, Ply8, _] )
->
  get_ply_state_count( win, Ply6) +
  get_ply_state_count( win, Ply8).

% --------------------------------------------------------------
% get_game_space_board_count_produced_by_player_1( Game_space )
% get_game_space_board_count_produced_by_player_2( Game_space )
%
%   You can also divide the boards in the game space into these
%   catagories:
%
%     Initial blank board (exactly one, in ply-0)
%     Boards produced by 1st player
%     Boards produced by 2nd player
%
%   Boards produced by player 1 can be catagorized further:
%
%     Player 2 must respond (state continuing)
%     Player 1 is the winner
%     Tie game
%
%   Boards produced by player 2 can also be catagorized further.
%   Player 2 never produces tie boards.
%
%     Player 1 must respond (state continuing)
%     Player 2 is the winner
%
%   Player 1 must also respond to the initial blank board.

get_game_space_board_count_produced_by_player_1(
    [_, Ply1, _, Ply3, _, Ply5, _, Ply7, _, Ply9] )
->
  get_ply_board_count( Ply1) +
  get_ply_board_count( Ply3) +
  get_ply_board_count( Ply5) +
  get_ply_board_count( Ply7) +
  get_ply_board_count( Ply9).

get_game_space_board_count_produced_by_player_2(
    [_, _, Ply2, _, Ply4, _, Ply6, _, Ply8, _] )
->
  get_ply_board_count( Ply2) +
  get_ply_board_count( Ply4) +
  get_ply_board_count( Ply6) +
  get_ply_board_count( Ply8).


% --------------------------------------------------------------
% Game spaces
% --------------------------------------------------------------
%
%   The game space is a directed graph of game boards.
%   Boards that are identical after rotation and reflection are
%   considered the same.
%
%   At each ply of the game there are a set of possible game
%   boards that can be achieved. These are divided into two
%   groups: winning boards (3 in a row), and other boards
%   which are continuing games, except after ply 9 when the
%   board is full and the game ends in a tie.
%
%   You can construct game-space filters from ply filters.

% --------------------------------------------------------------
% full_game_space( )
%
%   Returns a game space that describes every possible
%   tic-tac-toe game, even ones with very perverse sequences
%   of moves. The moves just have to be legal, with player 1
%   and player 2 taking turns. Games do not continue after a
%   player wins with 3 in-a-row.

full_game_space( ) ->
  Ply0 = init_ply( ),
  Ply1 = next_ply( Ply0),
  Ply2 = next_ply( Ply1),
  Ply3 = next_ply( Ply2),
  Ply4 = next_ply( Ply3),
  Ply5 = next_ply( Ply4),
  Ply6 = next_ply( Ply5),
  Ply7 = next_ply( Ply6),
  Ply8 = next_ply( Ply7),
  Ply9 = next_ply( Ply8),

  calc_game_space_predictions_and_leaf_counts(
    Ply0, Ply1, Ply2, Ply3, Ply4, Ply5, Ply6, Ply7, Ply8, Ply9).

% --------------------------------------------------------------
% smart_game_space( )
%
%   Returns a game space with all the mistake moves removed.
%   Without any mistakes, all game-paths lead to ties (assuming
%   normal-rules tic-tac-toe).
%   This game space doesn't represent all possible tie games
%   though since you can also get a tie if both players make
%   mistakes.

smart_game_space( ) ->
  filter_game_space(
    smart_init_moves,
    smart_moves,
    smart_moves,
    full_game_space( )).

% --------------------------------------------------------------
% smart_game_space_1st_player(
%     Start_instruction,
%     Filter_instruction,
%     Superset_game_space_with_predictions )
%
%   This generates game spaces that assumes we have control
%   over the 1st player, which allows us to discard all moves
%   by the 1st player that are not "smart".
%
%   A not-smart move leads a winning board into a tying or
%   losing situation. It can also lead a tying board into a
%   losing situation.
%
%   Start_instruction let's us choose how to trim the first-move
%   in the game space. It can have these values:
%     all_init_moves
%     smart_init_moves
%     corner_init_move
%     side_init_move
%     middle_init_move
%
%   Filter_instruction can be one of these values. Each
%   generates a different game space:
%     all_moves
%     single_move_simple
%     single_move_minimize_boards
%     smart_moves
%     smart_single_move_simple
%     smart_single_move_minimize_boards
%
%   The following will generate the full game space:
%     smart_game_space_1st_player(
%       all_init_moves
%       all_moves
%       full_game_space( ))
%
%   We need Full_game_space for the predictions stored for every
%   board in every ply. The predictions must be calculated
%   ahead of time.

smart_game_space_1st_player(
    Start_instruction,
    Filter_instruction,
    Superset_game_space_with_predictions )
->
  filter_game_space(
    Start_instruction,
    Filter_instruction,
    all_moves,
    Superset_game_space_with_predictions).

% --------------------------------------------------------------
% smart_game_space_2nd_player(
%     Start_instruction,
%     Filter_instruction,
%     Superset_game_space_with_predictions )
%
%   This generates game spaces that assumes we have control
%   over the 2nd player, which allows us to discard all moves
%   by the 2nd player that are not "smart".
%
%   A not-smart move leads a winning board into a tying or
%   losing situation. It can also lead a tying board into a
%   losing situation.
%
%   Start_instruction let's us choose how to trim the first-move
%   in the game space. It can have these values:
%     all_init_moves
%     smart_init_moves
%     corner_init_move
%     side_init_move
%     middle_init_move
%
%   Filter_instruction can be one of these values. Each
%   generates a different game space:
%     all_moves
%     single_move_simple
%     single_move_minimize_boards
%     smart_moves
%     smart_single_move_simple
%     smart_single_move_minimize_boards
%
%   We need Full_game_space for the predictions stored for every
%   board in every ply. The predictions must be calculated
%   ahead of time.

smart_game_space_2nd_player(
    Start_instruction,
    Filter_instruction,
    Superset_game_space_with_predictions )
->
  filter_game_space(
    Start_instruction,
    all_moves,
    Filter_instruction,
    Superset_game_space_with_predictions).


% --------------------------------------------------------------
% filter_game_space(
%     Start_instruction,
%     Filter_instruction_1st_player,
%     Filter_instruction_2nd_player,
%     Superset_game_space_with_predictions )
%
%   Start_instruction:
%     all_init_moves
%     smart_init_moves
%     corner_init_move
%     side_init_move
%     middle_init_move
%   Start_instruction is a filter instruction for player 1,
%   but only for the first move.
%
%   Filter_instruction_1st_player:
%   Filter_instruction_2nd_player:
%     all_moves
%     single_move_simple
%     single_move_minimize_boards
%     smart_moves
%     smart_single_move_simple
%     smart_single_move_minimize_boards
%   This instruction does not apply to the first move by the
%   1st player.
%
%   The single_minimize_boards choice minimizes the number of
%   boards in the next ply, which is not necessarily the same
%   as minimizing for the entire game space.
%
%   Another kind of single choice would be to choose the best
%   next move that won the fastest (lost lost the slowest).
%   This is the criteria tic:play( ) uses.
%
%   We could also just filter singles without first filtering
%   to just smart moves:
%     single_move_minimize_boards
%     single_move_simple
%
%   Superset_game_space_with_predictions
%     We need this for the predictions stored for every board in
%     every ply. The predictions must be calculated ahead of
%     time. Usually this is just a full game space.

filter_game_space(
    Start_instruction,
    Filter_instruction_1st_player,
    Filter_instruction_2nd_player,
    [ Ply0_predictions,
      Ply1_predictions, Ply2_predictions, Ply3_predictions,
      Ply4_predictions, Ply5_predictions, Ply6_predictions,
      Ply7_predictions, Ply8_predictions, Ply9_predictions ] )
->
  % Ply0 contains the empty board. It also contains the
  % next_boards for the empty board, which are the boards after
  % the first move.
  Ply0 =
    init_ply_filtered(
      Start_instruction, Ply0_predictions, Ply1_predictions),

  % Ply1 is generated from all the moves (next_boards) in Ply0.
  % Ply1 is all the boards with the first mark, and also all
  % the moves from there by the 2nd player.
  Ply1 =
    next_ply_filtered(
      Filter_instruction_2nd_player, Ply0,
      Ply1_predictions, Ply2_predictions),

  % Ply2 contains all the boards with 2 marks and all the moves
  % by the 1st player, which lead to ply3.
  % Player 2 defines which boards are in Ply2.
  % Player 1 defines which moves lead out of Ply2. So Player 1
  %   defines the transition from Ply2 -> Ply3.
  Ply2 =
    next_ply_filtered(
      Filter_instruction_1st_player, Ply1,
      Ply2_predictions, Ply3_predictions),

  Ply3 =
    next_ply_filtered(
      Filter_instruction_2nd_player, Ply2,
      Ply3_predictions, Ply4_predictions),

  Ply4 =
    next_ply_filtered(
      Filter_instruction_1st_player, Ply3,
      Ply4_predictions, Ply5_predictions),

  Ply5 =
    next_ply_filtered(
      Filter_instruction_2nd_player, Ply4,
      Ply5_predictions, Ply6_predictions),

  Ply6 =
    next_ply_filtered(
      Filter_instruction_1st_player, Ply5,
      Ply6_predictions, Ply7_predictions),

  Ply7 =
    next_ply_filtered(
      Filter_instruction_2nd_player, Ply6,
      Ply7_predictions, Ply8_predictions),

  Ply8 =
    next_ply_filtered(
      Filter_instruction_1st_player, Ply7,
      Ply8_predictions, Ply9_predictions),

  % We don't filter Ply9 because there are no moves leading
  % to Ply10. Filtering ONLY removes next moves, which means
  % it only removes boards from the NEXT ply, not THIS ply.
  % Since the next ply is ply10, which already has no boards
  % in it, this step is not necessary.
  %
  % We could call next_ply_filtered(..) here if we generated
  % an empty ply (no boards) and used it as ply-10.
  Ply9 = next_ply( Ply8),

  % This finishes the game space by setting values that we calc
  % while walking backwards thru the plys (from 9 thru 0).
  calc_game_space_predictions_and_leaf_counts(
    Ply0, Ply1, Ply2, Ply3, Ply4, Ply5, Ply6, Ply7, Ply8, Ply9).


% --------------------------------------------------------------
% Ply filtering and trimming
% --------------------------------------------------------------
%
%   We provide several filters that filter the next moves from
%   a ply. They do not filter the boards from the ply, just the
%   next moves.
%
%   These filters do not affect win/tie/lose boards because
%   they have not next moves. They only affect the set of moves
%   attached to a continuing board.
%
%   These filters never remove all the next moves.
%   A continuing board must have at least one next move.
%
%   The initial ply (ply-0) is special. It contains only one
%   board (the empty or starting board), with up to 9 next
%   moves (or 3 next moves if we are collapsing symmetry).
%
%   We provide several ways to filter the initial ply although
%   more are possible:
%     all_init_moves
%       There are 9 (or 3) init moves.
%
%     smart_init_moves
%       For normal rules this is the same as all_init_moves.
%       But for some some special rules it can be different.
%
%     corner_init_move
%     side_init_move
%     middle_init_move
%
%   Improvement:
%     We could provide a more general way to specify the moves
%     from the initial ply. Specifically, we could allow:
%       Position - integer 1-9
%       Position_list
%
%   Improvement:
%     A filtering instruction could be a list of filters to
%     apply one after another. For example:
%       [ smart_moves, single_move_minimize_boards ]
%
%   Improvement:
%     A game space should record how it has been filtered.
%     That info is useful when generating a report.
%
%   Improvement:
%     We could provide another filter to only keep optimal
%     moves. In the tic module, the game chooses a next move
%     trying to win the game quickest or lose slowest.
%     In this module, when we filter for smart moves, we keep
%     every move that leads to a win no matter how long it is.
%     An 'optimal' filter would only keep the next moves that
%     lead to the shortest win or the longest loss.
%     To do this we would have to change the prediction
%     calculation in this code to be like the prediiction
%     calculation in tic, where predictions tell you how many
%     moves until your win/loss.
%
%   Improvement:
%     We could provide a filter that got rid of center moves
%     unless there was no alternative. This is essentially
%     what the move-choice code in tic does.
%
%   Improvement:
%     We could provide a filter that always tried to block at
%     least one losing move when faced with a fork. This is
%     another thing the code in tic does, in order to make the
%     play feel more human.
%
%   Improvement?
%     We could experiment with filters based on leaf count.
%     We may want to find the games that minimize the board
%     counts (to make it easier on the computer) but maximize
%     leaf counts (to make the game feel less repetitious.

% --------------------------------------------------------------
% init_ply_filtered(
%     Start_instruction,
%     Ply0_superset_with_predictions,
%     Ply1_superset_with_predictions )
%
%   Returns the initial ply (ply0) of a game space.
%   The initial ply is the blank board and all the first moves.
%   (stored as next_boards in the ply dictionary).
%
%   Start_instruction
%     Lets us choose how to trim the first-move in the game
%     space. It can have these values:
%       all_init_moves
%       smart_init_moves
%       corner_init_move
%       side_init_move
%       middle_init_move

init_ply_filtered(
    Start_instruction,
    Ply0_superset_with_predictions,
    Ply1_superset_with_predictions)
->
  case Start_instruction of
    all_init_moves   -> init_ply( );
    corner_init_move -> init_ply_corner_move( );
    side_init_move   -> init_ply_side_move( );
    middle_init_move -> init_ply_middle_move( );

    smart_init_moves ->
      % For normal tic-tac-toe you can just return init_ply( ).
      % But for special rules you must filter.
      next_ply_filtered(
        smart_moves,
        before_init,
        Ply0_superset_with_predictions,
        Ply1_superset_with_predictions)
  end.

% --------------------------------------------------------------
% next_ply_filtered(
%     Filter_instruction,
%     Previous_ply,
%     This_ply_superset_with_predictions,
%     Next_ply_superset_with_predictions )
%
%   Calculates the next ply.
%   Trims some of the next moves (next_boards) from the next
%   ply we're creating.
%
%   There are 4 ways to calculate the next ply. The simplest way
%   is just to call next_ply( Previous_ply), which returns the
%   next ply will all possible next_boards (next moves) after
%   that ply. You can use this to generate the entire
%   un-filtered game space.
%
%   The three other ways to calculate the next ply involve
%   filtering. From this function you can choose between them
%   with the first arg Filter_instruction, which can take these
%   values:
%
%     all_moves
%       The next boards are not trimmed. The full ply is
%       generated from the previous ply, applying all possible
%       moves.
%
%     single_move_simple
%
%     single_move_minimize_boards
%
%     smart_moves
%       The next_boards (next moves) are trimmed so that a
%       possibly winning board will not stray to a tying or
%       losing path, and a winning/tying path will not
%       be downgraded to a losing board.
%
%     smart_single_move_simple
%       After the next_boards are trimmed to only the smart
%       moves, they are further trimmed so that each continuing
%       board has only a single move. A very simple algorithm
%       chooses that single move from the possible set of
%       smart moves.
%
%     smart_single_move_minimize_boards
%       As above, but the next moves are trimmed so as to
%       the number of boards in the next ply (after the one
%       returned) as much as possible.
%
%   Improvement: This could also provide options to apply
%   either of these to the unfiltered ply:
%     filter_ply_next_boards_to_singles( This_ply_unfiltered)
%     filter_ply_next_boards_to_singles_careful(
%                                        This_ply_unfiltered)

next_ply_filtered(
    Filter_instruction,
    Previous_ply,
    This_ply_superset_with_predictions,
    Next_ply_superset_with_predictions)
->
  This_ply_unfiltered = next_ply( Previous_ply),
  case Filter_instruction of
    all_moves -> This_ply_unfiltered;

    single_move_simple ->
      filter_ply_next_boards_to_singles( This_ply_unfiltered);

    single_move_minimize_boards ->
      filter_ply_next_boards_to_singles_careful(
        This_ply_unfiltered);

    _ ->
      This_ply_smart_moves_only =
        filter_ply_smart_moves_only(
          This_ply_unfiltered,
          This_ply_superset_with_predictions,
          Next_ply_superset_with_predictions),

      case Filter_instruction of
        smart_moves ->
          This_ply_smart_moves_only;

        smart_single_move_simple ->
          filter_ply_next_boards_to_singles(
            This_ply_smart_moves_only);

        smart_single_move_minimize_boards ->
          filter_ply_next_boards_to_singles_careful(
            This_ply_smart_moves_only)
      end
  end.

% --------------------------------------------------------------
% filter_ply_smart_moves_only(
%     This_ply_unfiltered,
%     This_ply_superset_with_predictions,
%     Next_ply_superset_with_predictions )
%
%   The superset plys have to contain all the boards in
%   This_ply_unfiltered, and all the boards have to have
%   accurate (calculated) win/tie/loss predictions.

filter_ply_smart_moves_only(
    This_ply_unfiltered,
    This_ply_predictions,
    Next_ply_predictions )
->
  % Only keeps the moves that lead to the next other player
  % losing. The next ply prediction is for the other player.
  Next_board_filter_for_wins =
    fun( Next_board ) ->
      % Next_prediction is for the next ply, so 'win' means
      % the next-next player, also the previous player, is
      % expected to win.
      Next_prediction =
        get_board_props_prediction(
          get_ply_board_props(
            Next_board, Next_ply_predictions)),
      case Next_prediction of
        win  -> false;
        tie  -> false;
        loss -> true
      end
    end,

  % Keep moves that don't let the other player win.
  % We don't have any moves that leads to the other player
  % losing or we would just keep those.
  Next_board_filter_for_ties =
    fun( Next_board ) ->
      Next_prediction =
        get_board_props_prediction(
          get_ply_board_props(
            Next_board, Next_ply_predictions)),
      case Next_prediction of
        win  -> false;
        tie  -> true
      end
    end,

  % We never need this in a tic-tac-toe game with normal
  % rules because both players always have a chance to
  % at least tie. But if we are filtering in a no-win
  % situation we need this.
  % There are two options here:
  %   Always return false and cut the game space off.
  %   Always return true and accept our loss.
  Next_board_filter_for_losses =
    fun( Next_board ) ->
      Next_prediction =
        get_board_props_prediction(
          get_ply_board_props(
            Next_board, Next_ply_predictions)),
      % We are in a no-win situation, where the other
      % player can force a win. So the smartest thing
      % to do is accept that we are going to lose.
      %
      % If we return false we will have to change some
      % code so we can deal with broken game spaces,
      % with continuing boards that have no next moves.
      case Next_prediction of
        % All next moves lead to a win by the other player.
        win -> true
      end
    end,

  % Predictions are foward looking, so 'win' means the
  % next player is expected to win and the previous player
  % is expected to lose.
  This_ply_map_filter_next_boards =
    fun( This_board, This_board_props ) ->
      This_prediction =
        get_board_props_prediction(
          get_ply_board_props(
            This_board, This_ply_predictions)),
      % Instead of dealing with loss here we could throw
      % an exception signaling that the game space is
      % broken.
      filter_board_props_next_boards(
        case This_prediction of
          win  -> Next_board_filter_for_wins;
          tie  -> Next_board_filter_for_ties;
          loss -> Next_board_filter_for_losses
        end,
        This_board_props)
    end,

  % Remove any following moves that are not "smart".
  map_ply(
    This_ply_map_filter_next_boards,
    This_ply_unfiltered).

% --------------------------------------------------------------
% filter_ply_next_boards_to_singles( Ply )
%
%   Takes all the continuing boards in a ply and discards all
%   next_boards except for the first one.
%   This is the simplest way to reduce a game space.

filter_ply_next_boards_to_singles( Ply ) ->
  map_ply(
    fun( _, Board_props ) ->
      filter_board_props_to_single_next_board( Board_props)
    end,
    Ply).

% --------------------------------------------------------------
% filter_ply_next_boards_to_singles_careful( Ply_original )
%
%   Implements a "smart" (ie complicated) algorithm to reduce
%   the next_boards in a game space.
%
%   Contrast this to filter_ply_next_boards_to_singles( Ply).

filter_ply_next_boards_to_singles_careful( Ply_original )
->
  % Make a ply that only has empty and singlular
  % next-board sets.
  Ply_singles =
    filter_ply(
      fun( _, Board_props ) ->
        Count =
          count_next_boards(
            get_board_props_next_boards( Board_props)),
        Count =< 1
      end,
      Ply_original),

  % If all the boards are now in the singles, we are done.
  Count_original = get_ply_board_count( Ply_original),
  Count_singles  = get_ply_board_count( Ply_singles),
  if Count_original =:= Count_singles -> Ply_singles;
  Count_original > Count_singles ->

    % Remove all the singles from the original.
    % We are left with boards that have multiple next-boards.
    Ply_multis = subtract_ply( Ply_original, Ply_singles),

    % Find all the boards in Ply_multis that share any target
    % boards with the Ply_singles over to the singles ply.
    Ply_to_move =
      find_ply_multi_boards_with_single_targets(
        Ply_multis, Ply_singles ),

    % Repeatedly remove boards with common targets from
    % Ply_multis and add them to Ply_singles.
    keep_trimming_until_no_more_multis(
      subtract_ply( Ply_multis, Ply_to_move),
      merge_ply_no_overlap( Ply_singles, Ply_to_move))
  end.

% --------------------------------------------------------------
% find_ply_multi_boards_with_single_targets(
%    Ply_multis, Ply_singles )
%
%   Part of a "smart" (ie complicated) algorithm to reduce the
%   next_boards in a game space.
%
%   Finds all the boards in Ply_multis that share any target
%   boards with Ply_singles. Stores them in a ply with
%   board_props with only a single target.

find_ply_multi_boards_with_single_targets
    ( Ply_multis, Ply_singles )
->
  % We need a set of all the next boards in Ply_singles.
  % This is the easiest way to get it.
  Ply_next_singles = next_ply( Ply_singles),

  % Folded over a set of boards.
  % Finds the first board in Ply_next_singles.
  Find_matching_next_board_fn =
    fun
      ( Board_look, not_found ) ->
        case is_board_in_ply( Board_look, Ply_next_singles) of
          true  -> Board_look;
          false -> not_found
        end;
      ( _, Board_found ) -> Board_found
    end,

  % Collect a dictionary (a ply) of boards and props.
  % Each board collected comes from Ply_multis, but has
  % a board_props with a single target board.
  Collect_ply_fn =
    fun( Board, Board_props, Ply_collect ) ->
      Next_boards =
        get_board_props_next_boards( Board_props),
      Next_board =
        fold_next_boards(
          Find_matching_next_board_fn, not_found, Next_boards),
      case Next_board of
        not_found -> Ply_collect;
        _ ->
          Board_props_singlet =
            set_board_props_next_boards(
              get_singlet_next_boards( Next_board),
              Board_props),
          ply_add_board( Board, Board_props_singlet, Ply_collect)
      end
    end,

  % Walk thru Ply_multi collecting any boards that have at least
  % one next_board that is also a next_board in Ply_singles.
  fold_ply(
    Collect_ply_fn,
    empty_ply( get_ply_index( Ply_multis)),
    Ply_multis).

% --------------------------------------------------------------
% find_ply_multi_boards_with_common_target(
%     Ply_multis, Next_board )
%
%   Part of a "smart" (ie complicated) algorithm to reduce the
%   next_boards in a game space.
%
%   Builds a ply of all the boards in Ply_multis that target
%   Next_board. The new ply will have Board_props with
%   next_boards sets targeting the single board Next_board.

find_ply_multi_boards_with_common_target
    ( Ply_multis, Next_board )
->
  % Collect a dictionary (a ply) of boards and props.
  % Each board collected comes from Ply_multis, but has
  % a board_props with a single target board.
  Collect_ply_fn =
    fun( Board, Board_props, Ply_collect ) ->
      Next_boards =
        get_board_props_next_boards( Board_props),
      case is_in_next_boards( Next_board, Next_boards) of
        false -> Ply_collect;
        true ->
          Board_props_singlet =
            set_board_props_next_boards(
              get_singlet_next_boards( Next_board),
              Board_props),
          ply_add_board( Board, Board_props_singlet, Ply_collect)
      end
    end,

  % Walk thru Ply_multis collecting any boards that can lead
  % to Next_board.
  fold_ply(
    Collect_ply_fn,
    empty_ply( get_ply_index( Ply_multis)),
    Ply_multis).

% --------------------------------------------------------------
% keep_trimming_until_no_more_multis( Ply_multis, Ply_singles )
%
%   Part of a "smart" (ie complicated) algorithm to reduce the
%   next_boards in a game space.
%
%   Tail-recusing loop that removes a small number of boards
%   (at least one) from Ply_multis and adds it to Ply_singles
%   in each iteration. The boards in Ply_multi all have more
%   than one target in their next_boards, but they are added
%   to Ply_singles with a single target.
%
%   This stops (and returns Ply_singles) when there are no
%   more boards in Ply_multis.

keep_trimming_until_no_more_multis( Ply_multis, Ply_singles ) ->

  % If there are no more boards in Ply_multis, we are done.
  case get_ply_board_count( Ply_multis) of 0 -> Ply_singles;
  _ ->
    % The following function is key. It reduces the number of
    % boards in the next ply to a minimum.
    { Next_board_to_peel, Src_count } =
      find_board_with_highest_src_count( next_ply( Ply_multis)),

    % If all the next_boards in Ply_multis are unique, we can
    % finish by just trimming the next_boards in a very simple
    % way, by discarding all next_boards after the head.
    if Src_count =:= 1 ->
      merge_ply_no_overlap( Ply_singles,
        filter_ply_next_boards_to_singles( Ply_multis));
    Src_count > 1 ->

      % Find all the boards in Ply_multis that target
      % Next_board_to_peel. We use a ply (instead of a
      % dictionary or a set) to keep track of these boards.
      Ply_to_move =
        find_ply_multi_boards_with_common_target(
          Ply_multis, Next_board_to_peel),

      % Recurse.
      keep_trimming_until_no_more_multis(
        subtract_ply( Ply_multis, Ply_to_move),
        merge_ply_no_overlap( Ply_singles, Ply_to_move))
    end
  end.

% --------------------------------------------------------------
% find_board_with_highest_src_count( Ply )
%
%   Part of a "smart" (ie complicated) algorithm to reduce the
%   next_boards in a game space.
%
%   Returns a pair:
%     { Board_from_ply, Src_count_for_board }
%
%   Do not call this with an empty ply. It will return
%   'unknown' if you do.
%
%   This is a critical function for the algorithm that reduces
%   the number of boards in a game space by deciding on all the
%   next moves for one of the players ahead of time.
%
%   Given a ply, this finds the board with the highest
%   src_count, which is a count of the number of boards
%   from the previous (generating) ply have moves leading
%   to this board.
%   This is used to build a (previous) ply with next moves
%   that lead to a few boards as possible.
%   So this acts to reduce the number of boards in the entire
%   game space.
%
%   When there are several boards with the same src_count to
%   choose from, this just returns the first it sees.
%   But there are other criteria we could us.
%   We could try to avoid middle moves (since they close off
%   the board), or better might be to choose the board with
%   the highest forward leaf_count. The leaf_count tells us
%   how many game-paths lie ahead for that board. The more
%   paths there are, the more interesting the game is for the
%   user.
%
%   The problem with leaf_paths is they can only be calculated
%   after the entire forward game-space is known. They are not
%   calculated in the Ply we get in this function.
%
%   And we cannot really calculate the entire game space (to
%   get the leaf_count) without calling this function to trim
%   the game space. So we're in a catch-22.
%
%   There are ways around this if we want to calculate huge
%   numbers of intermediate game spaces. Although probably a
%   better way is just use the leaf_counts from a superset
%   game-space calculated ahead of time.

find_board_with_highest_src_count( Ply ) ->
  fold_ply(
    fun
      ( Board, Board_props, unknown ) ->
        { Board, get_board_props_src_count( Board_props) };
      ( Board, Board_props, Pair_board_count ) ->
        Count = get_board_props_src_count( Board_props),
        if Count > element( 2, Pair_board_count) ->
          { Board, Count };
        true ->
          Pair_board_count
        end
    end,
    unknown,
    Ply).


% --------------------------------------------------------------
% Next ply calculations
% --------------------------------------------------------------

% --------------------------------------------------------------
% calc_game_space_predictions_and_leaf_counts(
%     Ply0, Ply1, Ply2, Ply3, Ply4,
%     Ply5, Ply6, Ply7, Ply8, Ply9 )
%
%   Calculates all the forward-looking properties (leaf_count
%   and prediction) for all boards in a game space.
%   This is the last thing you do when making a game space.

calc_game_space_predictions_and_leaf_counts(
    Ply0_, Ply1_, Ply2_, Ply3_, Ply4_,
    Ply5_, Ply6_, Ply7_, Ply8_, Ply9_ )
->
  Ply9 = Ply9_,
  Ply8 = calc_ply_predictions_and_leaf_counts( Ply9, Ply8_),
  Ply7 = calc_ply_predictions_and_leaf_counts( Ply8, Ply7_),
  Ply6 = calc_ply_predictions_and_leaf_counts( Ply7, Ply6_),
  Ply5 = calc_ply_predictions_and_leaf_counts( Ply6, Ply5_),
  Ply4 = calc_ply_predictions_and_leaf_counts( Ply5, Ply4_),
  Ply3 = calc_ply_predictions_and_leaf_counts( Ply4, Ply3_),
  Ply2 = calc_ply_predictions_and_leaf_counts( Ply3, Ply2_),
  Ply1 = calc_ply_predictions_and_leaf_counts( Ply2, Ply1_),
  Ply0 = calc_ply_predictions_and_leaf_counts( Ply1, Ply0_),

  [ Ply0, Ply1, Ply2, Ply3, Ply4,
    Ply5, Ply6, Ply7, Ply8, Ply9 ].

% --------------------------------------------------------------
% empty_ply( Ply_index )
%
%   Returns an empty (and illegitimate) ply. We use this as a
%   starting place when building a new ply. A ply in a game
%   space must contain at least one board, so this ply cannot
%   be part of a game space.

empty_ply( Ply_index ) ->
  { Ply_index, dict:new( ) }.

% --------------------------------------------------------------
% init_ply( )
%
%   Returns the initial ply (ply 0) in the game space.
%   The dictionary for ply 0 contains a single empty board.
%   The board_props for that empty board contains 3 next_boards,
%   each with a single mark (corner, side, and middle).
%
%   Use this with next_ply(..) to calculate a series of 10 ply
%   that describes the entire tic-tac-toe game space.

init_ply( ) ->
  Ply_index  = 0,
  Init_board = init_board( ),
  Prev_mark  = flip_mark( get_starting_mark( )),
  Init_props = init_board_props( Init_board, Prev_mark, 0),
  init_ply(
    Ply_index,
    dict:store( Init_board, Init_props, dict:new( ))).

% --------------------------------------------------------------
% init_ply_corner_move( )
% init_ply_side_move( )
% init_ply_middle_move( )
%
%   Returns initial plys (ply 0) where the initial empty board
%   in the dictionary has a single next_boards move instead of
%   the full set of 3 possible next moves.

init_ply_corner_move( ) ->
  init_ply_with_board_props(
    get_board_props_init_move_corner( )).

init_ply_side_move( ) ->
  init_ply_with_board_props(
    get_board_props_init_move_side( )).

init_ply_middle_move( ) ->
  init_ply_with_board_props(
    get_board_props_init_move_middle( )).

init_ply_with_board_props( Board_props ) ->
  Ply_index  = 0,
  Init_board = init_board( ),
  init_ply(
    Ply_index,
    dict:store( Init_board, Board_props, dict:new( ))).

% --------------------------------------------------------------
% next_ply( Prev_ply )
%
%   Given a ply, calculates the next ply in the game space.
%   All the next_boards in Prev_ply will appear in the next ply.
%
%   The board_props in the returned "next" ply will have all
%   possible next_boards filled in, along with state and
%   src_count.
%
%   The board_props leaf_count and prediction have to be
%   calculated later.

next_ply( before_init ) -> init_ply( );
next_ply( Prev_ply ) ->
  init_ply(
    get_ply_index( Prev_ply) + 1,
    init_dict_from_prev_ply( Prev_ply)).

init_dict_from_prev_ply( Prev_ply ) ->
  % This_mark is the mark (X or O) that was used to get from
  % Prev_ply to the ply we are constructing.
  Prev_mark = get_ply_next_mark( Prev_ply),

  % For every board in the newly constructed ply, create a
  % board_props entry.
  dict:map(
    fun( Board, Src_count ) ->
      init_board_props( Board, Prev_mark, Src_count)
    end,
    init_dict_from_prev_dict( get_ply_dict( Prev_ply))).

% For every dictionary entry in the previous ply, get
% the board_props, which contains a set of next_boards.
init_dict_from_prev_dict( Prev_dict ) ->
  dict:fold(
    fun( _, Board_props, Dict_outer ) ->
      collect_dict_from_next_boards( Board_props, Dict_outer)
    end,
    dict:new( ),
    Prev_dict).

% Collect all the next_boards into the dictionary.
% Keep track of the source count.
collect_dict_from_next_boards( Board_props, Dict_init ) ->
  fold_next_boards(
    fun( Board, Dict_collect ) ->
      dict:update_counter( Board, 1, Dict_collect)
    end,
    Dict_init,
    get_board_props_next_boards( Board_props)).

% --------------------------------------------------------------
% calc_ply_predictions_and_leaf_counts( Next_ply, This_ply )
%
%   Call this after you have built the plys that describe a
%   game space. This will calculate the forward-looking values
%   (leaf_count and prediction) stored with every board in
%   This_ply.
%
%   This will do nothing for the last ply.
%   Next_ply must be calculated first.

calc_ply_predictions_and_leaf_counts( Next_ply, This_ply ) ->
  map_ply(
    fun( _, Board_props ) ->
      fill_in_board_props_forward_props( Next_ply, Board_props)
    end,
    This_ply).


% --------------------------------------------------------------
% Ply interface
% --------------------------------------------------------------
%
%   A ply contains:
%
%     ply_index - integer, 0-9.
%       How many marks are on the boards in this ply.
%
%     dict
%       A dictionary of boards in this ply. Each board is
%       associated with a board_props tuple.

% --------------------------------------------------------------
% Getters for Ply

get_ply_index( Ply ) -> element( 1, Ply).
get_ply_dict(  Ply ) -> element( 2, Ply).

get_ply_prev_mark( Ply ) -> prev_ply_mark( get_ply_index( Ply)).
get_ply_next_mark( Ply ) -> next_ply_mark( get_ply_index( Ply)).

% --------------------------------------------------------------
% init_ply( Ply_index, Dict )
% set_ply_dict( Dict, Ply )
%
%   A ply is a 2-tuple (pair). It's an index (zero-based) and
%   a dictionary associating all the boards at that ply with
%   a board_props.
%   The ply_index tells you how many marks are on the boards in
%   the ply dictionary. Ply0 always has only one board, with no
%   marks on it. Ply9 contains only boards with 9 marks (and
%   thus no empty spaces).

init_ply( Ply_index, Dict ) ->
  { Ply_index, Dict }.

set_ply_dict( Dict, Ply ) ->
  init_ply( get_ply_index( Ply), Dict).

% --------------------------------------------------------------
% is_board_in_ply( Board, Ply )
% get_ply_board_props( Board, Ply )
%
%   Board_props is the object (tuple) associated with the Board
%   in the ply dictionary.

is_board_in_ply( Board, Ply ) ->
  dict:is_key( Board, get_ply_dict( Ply)).

get_ply_board_props( Board, Ply ) ->
  dict:fetch( Board, get_ply_dict( Ply)).

% --------------------------------------------------------------
% ply_add_board( Board, Board_props, Ply )
%
%   Adds a new Board and Board_props to the Ply dictionary.
%   Replaces Board_props if Board is already in the dictionary.

ply_add_board( Board, Board_props, Ply ) ->
  set_ply_dict(
    dict:store( Board, Board_props, get_ply_dict( Ply)), Ply).

% --------------------------------------------------------------
% ply_remove_board( Board, Ply )
%
%   Removes Board from Ply.
%   It's OK if Board is not in Ply.

ply_remove_board( Board, Ply ) ->
  set_ply_dict(
    dict:erase( Board, get_ply_dict( Ply)), Ply).

% --------------------------------------------------------------
% fold_ply( Fold_fn, Init_value, Ply )
%
%   Fold_fn( Board, Board_props, Collect_init ) -> Collect_next

fold_ply( Fold_fn, Init_value, Ply ) ->
  dict:fold( Fold_fn, Init_value, get_ply_dict( Ply)).

% --------------------------------------------------------------
% map_ply( Map_fn, Ply )
%
%   Calculate a new board_props for every board in Ply.
%   Map_fn( Board, Board_props ) -> Board_props

map_ply( Map_fn, Ply ) ->
  set_ply_dict( dict:map( Map_fn, get_ply_dict( Ply)), Ply).

% --------------------------------------------------------------
% filter_ply( Filter_fn, Ply )
%
%   Filter out some Boards from Ply.
%   Filter_fn( Board, Board_props ) -> true/false

filter_ply( Filter_fn, Ply ) ->
  set_ply_dict(
    dict:filter( Filter_fn, get_ply_dict( Ply)),
    Ply).

% --------------------------------------------------------------
% merge_ply( Merge_fn, Ply1, Ply2 )
%
%   Combines all the Boards and Board_props from two plys.
%   If any board is in both ply, the Merge_fn(..) function will
%   be called to resolve what should be stored as Board_props.
%
%   Merge_fn( Board, Board_props1, Board_props2 ) ->
%     Board_props_to_store
%
%   Both plys should have the same ply_index, or this operation
%   doesn't make sense.

merge_ply( Merge_fn, Ply1, Ply2 ) ->
  set_ply_dict(
    dict:merge( Merge_fn,
      get_ply_dict( Ply1), get_ply_dict( Ply2)),
    Ply1).

% --------------------------------------------------------------
% merge_ply_no_overlap( Ply1, Ply2 )
%
%   Combines all the Boards and Board_props from two plys into
%   one ply. Error if the two plys have any overlap.

merge_ply_no_overlap( Ply1, Ply2 ) ->
  merge_ply(
    fun( false, false, false ) -> ok end,
    Ply1,
    Ply2).

% --------------------------------------------------------------
% subtract_ply( Ply_start, Ply_remove )
%
%   Removes all boards in Ply_remove from Ply_start.
%   It's OK if Ply_remove holds boards not in Ply_start.
%   Although this does not check, the ply_index values for both
%   plys should be the same or there will be no matching boards.

subtract_ply( Ply_start, Ply_remove ) ->
  filter_ply(
    fun( Board, _ ) ->
      not is_board_in_ply( Board, Ply_remove)
    end,
    Ply_start).

% --------------------------------------------------------------
% count_ply( Count_predicate, Ply )
%
%   Count_predicate( Board, Board_props ) -> true/false

count_ply( Count_predicate, Ply ) ->
  fold_ply(
    fun( Board, Board_props, Count ) ->
      case Count_predicate( Board, Board_props) of
        true  -> Count + 1;
        false -> Count
      end
    end,
    0,
    Ply).

% --------------------------------------------------------------
% sum_ply( Sum_fn, Ply )
%
%   Sum_fn( Board, Board_props ) -> integer

sum_ply( Sum_fn, Ply ) ->
  fold_ply(
    fun( Board, Board_props, Sum ) ->
      Sum + Sum_fn( Board, Board_props)
    end,
    0,
    Ply).

% --------------------------------------------------------------
% get_ply_board_count( Ply )
%
%   How many (canonical) boards are in this ply.
%   Includes all boards, continuing and finished.

get_ply_board_count( Ply ) ->
  dict:size( get_ply_dict( Ply)).

% --------------------------------------------------------------
% get_ply_state_count( State, Ply )
%
%   Counts how many boards in a Ply have a specified State.
%   So get_ply_state_count( tie, Ply) tells you how many boards
%   in this ply were tied in the last move. Of course this is
%   always zero except in the last ply, since ties can only
%   occur in the last ply in tic-tac-toe.

get_ply_state_count( State, Ply ) ->
  count_ply(
    fun( _, Board_props ) ->
      get_board_props_state( Board_props) =:= State
    end,
    Ply).

% --------------------------------------------------------------
% get_ply_prediction_count( Prediction, Ply )
%
%   Counts how many boards in the Ply have a prediction that
%   matches Prediction. So get_ply_prediction_count( tie, Ply)
%   tells you how many boards in the ply are predicted to end
%   in a tie.
%
%   Another useful number might be the number of forward paths
%   (leaf_counts) in the game_space are predicted to end in a
%   win/tie/loss.

get_ply_prediction_count( Prediction, Ply ) ->
  count_ply(
    fun( _, Board_props ) ->
      get_board_props_prediction( Board_props) =:= Prediction
    end,
    Ply).

% --------------------------------------------------------------
% get_ply_leaf_count( Ply )
%
%   Sums the leaf_counts for all the boards in the Ply.
%   A leaf_count for a board is the number of forward paths from
%   this board to all finished games in the game space.

get_ply_leaf_count( Ply ) ->
  sum_ply(
    fun( _, Board_props ) ->
      get_board_props_leaf_count( Board_props)
    end,
    Ply).

% --------------------------------------------------------------
% get_ply_src_count( Ply )
%
%   Sums the src_counts for all the boards in the ply.

get_ply_src_count( Ply ) ->
  sum_ply(
    fun( _, Board_props ) ->
      get_board_props_src_count( Board_props)
    end,
    Ply).

% --------------------------------------------------------------
% report_ply( Ply )
%
%   Reports a basic summary of what's in a Ply. Does not
%   display all the boards in the ply.

report_ply( Ply ) ->
  case get_ply_index( Ply) of
    0 -> report_ply_0( Ply);
    9 -> report_ply_9( Ply);
    _ -> report_ply_detail( Ply)
  end.

report_ply_detail( Ply ) ->
  Ply_index    = get_ply_index( Ply),
  Player       = case Ply_index band 1 of 0 -> 2; 1 -> 1 end,
  Player_other = case Ply_index band 1 of 0 -> 1; 1 -> 2 end,
  Board_count  = get_ply_board_count( Ply),
  Cont_count   = get_ply_state_count( continuing, Ply),
  Win_states   = get_ply_state_count( win, Ply),
  Tie_predict  = get_ply_prediction_count( tie, Ply),
  Win_predict  = get_ply_prediction_count( loss, Ply),
  Win_after    = Win_predict - Win_states,
  Loss_predict = get_ply_prediction_count( win, Ply),

  write_line( "  Player ~w moves, leading to ply ~w",
    Player, Ply_index),

  write_string( "    ~w boards ", Board_count),
  if Board_count =:= Cont_count ->
    if Tie_predict =:= Cont_count ->
      write_line( "(all continue to ties)");
    true ->
      write_line( "(all continue)")
    end;
  true ->
    if Tie_predict =:= Cont_count ->
      write_line( "(~w continuing to ties)", Cont_count);
    true ->
      write_line( "(~w continuing)", Cont_count)
    end
  end,

  if Win_states =/= 0 ->
    write_line( "      ~w boards won by player ~w",
      Win_states, Player);
  true -> ok end,

  if Tie_predict =/= 0 ->
    if Tie_predict =/= Cont_count ->
      write_line(
        "      ~w boards lead to ties", Tie_predict);
    true -> ok end;
  true -> ok end,

  if Win_after =/= 0 ->
    write_line(
      "      ~w boards lead to a win by player ~w",
      Win_after, Player);
  true -> ok end,

  if Loss_predict =/= 0 ->
    write_line(
      "      ~w boards lead to a win by player ~w",
      Loss_predict, Player_other);
  true -> ok end.

% X moves next
report_ply_0( Ply ) ->
  write_line( "  Starting blank board"),
  write_line( "    Total number of game paths: ~w",
    get_ply_leaf_count( Ply)).

% X just moved
report_ply_9( Ply ) ->
  Tie_count = get_ply_state_count( tie, Ply),
  Win_count = get_ply_state_count( win, Ply),

  write_line( "  Player 1 moves (last move)"),

  if 0 =/= Tie_count ->
    write_line( "    ~w tie boards", Tie_count);
  true -> ok end,

  if 0 =/= Win_count ->
    write_line( "    ~w boards won by player 1", Win_count);
  true -> ok end.

% --------------------------------------------------------------
% report_ply_boards( Ply )
%
%   Reports on all the boards in a ply.

report_ply_boards( Ply ) ->
  write_line( ),
  write_line( "  Boards in ply ~w", get_ply_index( Ply)),

  { Win_boards, Tie_boards, Continuing_boards } =
    lists:foldl(
      fun( Pair, Tuple ) ->
        { _, Board_props } = Pair,
        Index =
          case get_board_props_state( Board_props) of
            win        -> 1;
            tie        -> 2;
            continuing -> 3
          end,
        setelement( Index, Tuple,
          [Pair | element( Index, Tuple)])
      end,
      erlang:make_tuple( 3, []),
      dict:to_list( get_ply_dict( Ply))),

  lists:foreach(
    fun( {Board, Board_props} ) ->
      report_board( Board, Board_props),
      write_line( )
    end,
    lists:sort( Win_boards)),

  lists:foreach(
    fun( {Board, Board_props} ) ->
      report_board( Board, Board_props),
      write_line( )
    end,
    lists:sort( Tie_boards)),

  lists:foreach(
    fun( {Board, Board_props} ) ->
      report_board( Board, Board_props),
      write_line( )
    end,
    lists:sort( Continuing_boards)).


% --------------------------------------------------------------
% Next_boards
% --------------------------------------------------------------
%
%   Next_boards are part of board_props.
%   Each next_board represents a "next move".

% --------------------------------------------------------------
% calc_next_boards( Mark, Src_board )
%
%   Returns a Next_boards set. This is a set of canonical boards
%   derived from Src_board with one more mark on it. So if
%   Src_board is full this will return an empty set.

calc_next_boards( Mark, Src_board ) ->
  lists:foldl(
    fun( Position, Set_of_trg_boards ) ->
      case is_board_marked_at( Position, Src_board ) of
        false ->
          add_to_next_boards(
            mark_board_at( Position, Mark, Src_board),
            Set_of_trg_boards);
        true ->
          Set_of_trg_boards
      end
    end,
    get_empty_next_boards( ),
    lists:seq( 1, 9)).

% --------------------------------------------------------------
% add_to_next_boards( Board, Next_boards )

add_to_next_boards( Board, Next_boards ) ->
  ordsets:add_element(
    get_canonical_board( Board), Next_boards).

% --------------------------------------------------------------
% is_in_next_boards( Board, Next_boards )

is_in_next_boards( Board, Next_boards ) ->
  ordsets:is_element( Board, Next_boards).

% --------------------------------------------------------------
% get_empty_next_boards( )

get_empty_next_boards( ) ->
  ordsets:new( ).

% --------------------------------------------------------------
% get_singlet_next_boards( Board )

get_singlet_next_boards( Board ) ->
  add_to_next_boards( Board, get_empty_next_boards( )).

% --------------------------------------------------------------
% count_next_boards( Next_boards )

count_next_boards( Next_boards ) ->
  ordsets:size( Next_boards).

% --------------------------------------------------------------
% has_next_board( Next_boards )
%
%   We could also call this something like:
%     is_set_of_next_boards_not_empty( Next_boards )

has_next_board( Next_boards ) ->
  count_next_boards( Next_boards) =/= 0.

% --------------------------------------------------------------
% get_next_boards_first_board( Next_boards )

get_next_boards_first_board( Next_boards ) ->
  % Assumes 'first' is never considered a board.
  % We could generalize this for any fold by using make_ref( ).
  fold_next_boards(
    fun
      ( Board, first ) -> Board;
      ( _    , Board ) -> Board
    end,
    first,
    Next_boards).

% --------------------------------------------------------------
% fold_next_boards( Fold_fn, Accumulate, Next_boards )
%
%   Iterates over the set of Next_boards. Order of iteration
%   is not specified because the order of the set of boards
%   in Next_boards is not specified.
%
%   The fold function should look like this:
%     Fold_fn( Board, Accumulate_0 ) -> Accumulate_1

fold_next_boards( Fold_fn, Accumulate, Next_boards ) ->
  ordsets:fold( Fold_fn, Accumulate, Next_boards).

% --------------------------------------------------------------
% filter_next_boards( Filter_pred, Next_boards )
%
%   Filter_pred looks like this:
%     Filter_pred( Board ) -> true or false

filter_next_boards( Filter_pred, Next_boards ) ->
  ordsets:filter( Filter_pred, Next_boards).


% --------------------------------------------------------------
% Board_props interface
% --------------------------------------------------------------
%
%   A board_props is a tuple describing the next moves a board
%   may take. These tuples are paired with a board in the ply
%   dictionary. Each board_props tuple includes:
%
%     next_boards
%       A set (ordsets) of boards that we'll get after the next
%       move. This might include all possible moves, or the
%       set might be restricted to only wise moves, or to only
%       the moves we want to consider.
%
%       Instead of storing next_boards we could store next
%       moves. From the next move we'd like to know:
%         The resulting board
%         Resulting state
%         Predicted result(s)
%         How many game paths make this move
%
%     src_count
%       Number of predecessors.
%       Number of source boards in the previous ply that lead
%       to this board after one move.
%
%     leaf_count
%       Number of paths from here to a leaf.
%       The number of game paths from here to a finished game.
%       This is always 1 if state is win or tie.
%       For continuing boards this is calculated after all the
%       plys in the game-space are set up.
%       Possible values:
%         1       - for boards with states win or tie
%         unknown - for continuing boards (before calculation)
%         >= 1    - for continuing boards
%
%     state
%       An atom that tells us about the dictionary-entry board.
%       One of these values:
%         win - the board has 3-in-a-row
%         tie - the board is full with no 3-in-a-row
%         continuing
%       Win means the last move won. This is different from
%       the prediction prop which talks about the next move.
%
%       If state is win or tie, the next_boards set must be
%       empty. Otherwise next_boards must not be empty.
%       State tie can only occur in the last ply.
%       State win can not occur in the last ply, and really
%       only in plys 5, 6, 7, and 8.
%
%     prediction
%       An atom that tells us how this game will end up,
%       assuming it is played without mistakes.
%       One of these values:
%         win
%         loss
%         tie
%         unknown
%       This is a prediction for the next-move player. So in
%       ply0, the predictions will be for the first player.
%       Even plys hold predictions for the first player, and
%       odd plys for the 2nd player.

% --------------------------------------------------------------
% Getters for Board_props
%
%   The properties of board_props are:
%     next_boards
%     src_count
%     leaf_count
%     state
%     prediction

get_board_props_next_boards( Board_props ) ->
  element( 1, Board_props).

get_board_props_src_count( Board_props ) ->
  element( 2, Board_props).

get_board_props_leaf_count( Board_props ) ->
  element( 3, Board_props).

get_board_props_state( Board_props ) ->
  element( 4, Board_props).

get_board_props_prediction( Board_props ) ->
  element( 5, Board_props).

% --------------------------------------------------------------
% init_board_props( Board, Prev_mark, Src_count )
%
%   Calculates the board_props to store with a board when
%   building a ply. Does not include forward-looking properties
%   leaf_count and prediction. These have to be calculated
%   later, starting with the last ply and working backwards.

init_board_props( Board, Prev_mark, Src_count ) ->
  case is_board_won_by( Prev_mark, Board) of
    true  ->
      % This is a winning board.
      init_board_props_win( Src_count);
    false ->
      % This is a tie board if this the last ply.
      % Otherwise this is a continuing board.
      Next_mark   = flip_mark( Prev_mark),
      Next_boards = calc_next_boards( Next_mark, Board),
      case has_next_board( Next_boards) of
        false ->
          init_board_props_tie( Src_count);
        true  ->
          init_board_props_continuing( Src_count, Next_boards)
      end
  end.

init_board_props_win( Src_count) ->
  % If this board is won (state is win), then it is a loss for
  % the player who moves next. That is why the prediction is
  % loss instead of win. Win marks this board as finished,
  % loss means it is a loss for the NEXT player, not the last.
  { get_empty_next_boards( ), Src_count, 1, win, loss }.

init_board_props_tie( Src_count ) ->
  { get_empty_next_boards( ), Src_count, 1, tie, tie }.

init_board_props_continuing( Src_count, Next_boards ) ->
  { Next_boards, Src_count, unknown, continuing, unknown }.

% --------------------------------------------------------------
% get_board_props_init_move_corner( )
% get_board_props_init_move_side( )
% get_board_props_init_move_middle( )
%
%   Returns boards with the three possible first moves.
%     X..  .X.  ...
%     ...  ...  .X.
%     ...  ...  ...
%
%   We could generalize this to provide any set of initial
%   moves by specifying position:
%     get_board_props_init_move_positions( Pos)
%     get_board_props_init_move_positions( Pos_list)

get_board_props_init_move_corner( ) ->
  get_board_props_init_move_( get_board_init_move_corner( )).

get_board_props_init_move_side( ) ->
  get_board_props_init_move_( get_board_init_move_side( )).

get_board_props_init_move_middle( ) ->
  get_board_props_init_move_( get_board_init_move_middle( )).

get_board_props_init_move_( Board ) ->
  { get_singlet_next_boards( get_canonical_board( Board)),
    1, unknown, continuing, unknown
  }.

% --------------------------------------------------------------
% set_board_props_next_boards( Next_boards, Board_props )
%
%   Changes the set of next_boards in a Board_props.
%   For non-continuing (win/tie) boards the board_props should
%   always have an empty set of next_boards. For continuing
%   boards the set should always be non-empty.

set_board_props_next_boards( Next_boards, Board_props ) ->
  { Next_boards,
    get_board_props_src_count(  Board_props),
    get_board_props_leaf_count( Board_props),
    get_board_props_state(      Board_props),
    get_board_props_prediction( Board_props)
  }.

% --------------------------------------------------------------
% fill_in_board_props_forward_props( Next_ply, Board_props )
%
%   Calculates the leaf_count and prediction properties for
%   board_props. Assumes all the next_boards are in Next_ply
%   and have leaf_counts and predictions already calculated.

fill_in_board_props_forward_props( Next_ply, Board_props ) ->
  case get_board_props_state( Board_props) of
    continuing ->
      % It would be a little more efficient to calculate both
      % the leaf_count and prediction in the same in the same
      % function since both functions look up all the
      % next_boards in Next_ply.
      { get_board_props_next_boards( Board_props),
        get_board_props_src_count( Board_props),
        calc_board_leaf_count( Next_ply, Board_props),
        get_board_props_state( Board_props),
        calc_board_prediction( Next_ply, Board_props)
      };
    _ ->
      % Non-continuing (win and tie) boards already have
      % leaf_count and prediction values. For these, the set of
      % next_boards is always empty, leaf_count is always 1, and
      % prediction is either loss (for state win) or tie.
      Board_props
  end.

% --------------------------------------------------------------
% calc_board_prediction( Next_ply, Src_board_props )
%
%   Calculates the win/tie/loss prediction for Src_board_props.
%   Assumes all the next_boards are in Next_ply, and that they
%   all have calculated predictions.
%
%   Remember a win at this ply is the same as forcing a loss at
%   the next ply. And a loss at this ply means the other player
%   can force a win for himself at the next ply.

calc_board_prediction( Next_ply, Src_board_props ) ->
  fold_next_boards(
    fun
      ( _ , win ) -> win;

      ( Next_board, tie ) ->
        Next_props = get_ply_board_props( Next_board, Next_ply),
        case get_board_props_prediction( Next_props) of
          loss -> win;
          _    -> tie
        end;

      ( Next_board, _ ) ->
        Next_props = get_ply_board_props( Next_board, Next_ply),
        case get_board_props_prediction( Next_props) of
          loss -> win;
          tie  -> tie;
          win  -> loss
        end
    end,
    unknown,
    get_board_props_next_boards( Src_board_props)).

% --------------------------------------------------------------
% calc_board_leaf_count( Next_ply, Src_board_props )
%
%   Assumes all the next_boards are in Next_ply, and the
%   leaf_counts in the board_props in Next_ply are already
%   calculated.
%
%   Only works for continuing boards.
%   Returns 0 for win/tie boards (instead of 1, the correct
%   answer). You never have to calculate leaf_count for win/tie
%   next_boards.

calc_board_leaf_count( Next_ply, Src_board_props ) ->
  fold_next_boards(
    fun( Next_board, Sum ) -> Sum +
      get_board_props_leaf_count(
        get_ply_board_props( Next_board, Next_ply))
    end,
    0,
    get_board_props_next_boards( Src_board_props)).

% --------------------------------------------------------------
% filter_board_props_next_boards( Filter_pred, Board_props )
%
%   This removes next_boards that do not pass Filter_pred.
%   Filter_pred only gets to see the boards in next_boards, not
%   the source board.
%   Filter_pred only gets to the the next boards one at a time,
%   so it cannot compare all the next boards and just choose the
%   ones it likes.
%
%   It is not legal to filter out all the boards in next_boards.
%   Continuing boards should have at least one next_board.
%
%   Filter_pred( Board ) -> true/false
%     where Board is from a set of next_boards.

filter_board_props_next_boards( Filter_pred, Board_props ) ->
  case get_board_props_state( Board_props) of
    % Only continuing props have non-empty next_boards.
    % This clears leaf_count and prediction.
    continuing ->
      { filter_next_boards(
          Filter_pred,
          get_board_props_next_boards( Board_props)),
        get_board_props_src_count( Board_props),
        unknown,
        continuing,
        unknown
      };
    _ ->
      Board_props
  end.

% --------------------------------------------------------------
% filter_board_props_to_single_next_board( Board_props )
%
%   If Board_props has more than one board in next_boards, this
%   discards all but the first one.
%   This also clears leaf_count and prediction board_props, but
%   only for continuing board_props.

filter_board_props_to_single_next_board( Board_props ) ->
  case get_board_props_state( Board_props) of
    % Only continuing Board_props have non-empty next_boards,
    % and they always have at least one next_board.
    % This chops off all next_boards after the first one.
    % This also clears leaf_count and prediction, which are the
    % forward-looking properties that depend on next_boards.
    % Leaf_count and prediction are cleared even if next_boards
    % starts with only a single board (and is thus not changed
    % here).
    continuing ->
      { get_singlet_next_boards(
          get_next_boards_first_board(
            get_board_props_next_boards( Board_props))),
        get_board_props_src_count( Board_props),
        unknown,
        continuing,
        unknown
      };
    _ ->
      % Board_props for non-continuing (win/tie) boards have no
      % next_boards, so there's no point in trimming them.
      Board_props
  end.


% --------------------------------------------------------------
% Mark interface
% --------------------------------------------------------------
%
%   A Mark is the mark you put on a board. It is one of:
%     empty   - zempty
%     x_mark  - amark
%     o_mark  - bmark
%
%   We use amark, bmark, and zempty because that gives us the
%   ordering we want. When we choose the canonical board, we
%   choose the reflected/rotated board that compares least.

-define( X_MARK, amark).
-define( O_MARK, bmark).
-define( EMPTY, zempty).

% --------------------------------------------------------------
% get_starting_mark( )
%
%   We start with an X.

get_starting_mark( ) -> ?X_MARK.

% --------------------------------------------------------------
% flip_mark( Mark )

flip_mark( ?X_MARK ) -> ?O_MARK;
flip_mark( ?O_MARK ) -> ?X_MARK.

% --------------------------------------------------------------
% prev_ply_mark( Ply_index )
%
%   Tells you the mark used to get from the previous ply to
%   this one. Ply_index must be 1..9. If Ply_index is 1, returns
%   the mark used on the empty board (ply 0) to get to the
%   current board (ply 1).
%
%   Returns:
%     Ply_index is odd -> x_mark
%     Ply_index is odd -> o_mark
%
%   Since the first move is from ply 0 to ply 1, when a board
%   has only one mark, that mark is X (x_mark). X always starts.

prev_ply_mark( Ply_index )
    when (1 =< Ply_index), (Ply_index =< 9)
->
  case Ply_index band 1 of
    0 -> ?O_MARK;
    1 -> ?X_MARK
  end.

% --------------------------------------------------------------
% next_ply_mark( Ply_index )
%
%   Tells you the next mark to put on the boards in this ply.
%   Ply_index must be 0..8. The board is full at ply 9, so there
%   is no next mark.

next_ply_mark( Ply_index ) ->
  prev_ply_mark( Ply_index + 1).

% --------------------------------------------------------------
% get_mark_string( Mark )
%
%   Returns a one-character string.

get_mark_string( ?X_MARK ) -> "X";
get_mark_string( ?O_MARK ) -> "O";
get_mark_string( ?EMPTY  ) -> " ".


% --------------------------------------------------------------
% Board interface
% --------------------------------------------------------------
%
%   A Board is a 9-tuple, representing a 3x3 tic-tac-toe board.
%   (9 elements is 3 rows times 3 columns.)

% --------------------------------------------------------------
% init_board( )

init_board( ) ->
  { ?EMPTY, ?EMPTY, ?EMPTY,
    ?EMPTY, ?EMPTY, ?EMPTY,
    ?EMPTY, ?EMPTY, ?EMPTY
  }.

% --------------------------------------------------------------
% get_board_init_move_corner( )
% get_board_init_move_side( )
% get_board_init_move_middle( )

get_board_init_move_corner( ) ->
  { get_starting_mark( ), ?EMPTY, ?EMPTY,
    ?EMPTY              , ?EMPTY, ?EMPTY,
    ?EMPTY              , ?EMPTY, ?EMPTY
  }.

get_board_init_move_side( ) ->
  { ?EMPTY, get_starting_mark( ), ?EMPTY,
    ?EMPTY, ?EMPTY              , ?EMPTY,
    ?EMPTY, ?EMPTY              , ?EMPTY
  }.

get_board_init_move_middle( ) ->
  { ?EMPTY, ?EMPTY              , ?EMPTY,
    ?EMPTY, get_starting_mark( ), ?EMPTY,
    ?EMPTY, ?EMPTY              , ?EMPTY
  }.

% --------------------------------------------------------------
% is_board_marked_at( Position, Board )

is_board_marked_at( Position, Board ) ->
  element( Position, Board) =/= ?EMPTY.

% --------------------------------------------------------------
% mark_board_at( Position, Mark, Board )
%
%   Returns a new board with Mark at Position.

mark_board_at( 1, M,
  { _,_2,_3,_4,_5,_6,_7,_8,_9} ) ->
  { M,_2,_3,_4,_5,_6,_7,_8,_9};
mark_board_at( 2, M,
  {_1, _,_3,_4,_5,_6,_7,_8,_9} ) ->
  {_1, M,_3,_4,_5,_6,_7,_8,_9};
mark_board_at( 3, M,
  {_1,_2, _,_4,_5,_6,_7,_8,_9} ) ->
  {_1,_2, M,_4,_5,_6,_7,_8,_9};
mark_board_at( 4, M,
  {_1,_2,_3, _,_5,_6,_7,_8,_9} ) ->
  {_1,_2,_3, M,_5,_6,_7,_8,_9};
mark_board_at( 5, M,
  {_1,_2,_3,_4, _,_6,_7,_8,_9} ) ->
  {_1,_2,_3,_4, M,_6,_7,_8,_9};
mark_board_at( 6, M,
  {_1,_2,_3,_4,_5, _,_7,_8,_9} ) ->
  {_1,_2,_3,_4,_5, M,_7,_8,_9};
mark_board_at( 7, M,
  {_1,_2,_3,_4,_5,_6, _,_8,_9} ) ->
  {_1,_2,_3,_4,_5,_6, M,_8,_9};
mark_board_at( 8, M,
  {_1,_2,_3,_4,_5,_6,_7, _,_9} ) ->
  {_1,_2,_3,_4,_5,_6,_7, M,_9};
mark_board_at( 9, M,
  {_1,_2,_3,_4,_5,_6,_7,_8, _} ) ->
  {_1,_2,_3,_4,_5,_6,_7,_8, M}.

% --------------------------------------------------------------
% get_canonical_board( Board )
%
%   Returns a Board.
%
%   When ?c_symmetry_collapse is true:
%     Chooses one board from all the 8 rotations/reflections.
%
%     This greatly reduces the number of boards in each
%     ply and the total size of the game space by treating all
%     board rotations and reflections as equal.
%
%   When ?c_symmetry_collapse is false:
%     Simply returns Board.
%
%     This will make the game space much bigger (and
%     noticeably slower). But you have to do this if any of
%     the winning patterns are not expressed in all possible
%     reflections/rotations.
%
%   This is the only function that calls:
%     rotate_board(..)
%     reflect_board(..)

get_canonical_board( Board ) ->
  % Should we check ?c_patterns_have_symmetry as well as
  % ?c_symmetry_collapse? No, assume the user knows what
  % he is doing.
  case ?c_symmetry_collapse of
    false -> Board;
    true  ->
      Rot1 = rotate_board( Board),
      Rot2 = rotate_board( Rot1),
      Rot3 = rotate_board( Rot2),
      Ref0 = reflect_board( Board),
      Ref1 = rotate_board( Ref0),
      Ref2 = rotate_board( Ref1),
      Ref3 = rotate_board( Ref2),
      lists:min(
        [Board, Rot1, Rot2, Rot3, Ref0, Ref1, Ref2, Ref3])
  end.

% --------------------------------------------------------------
% rotate_board(  Board ) - rotates Board quarter turn clockwise
% reflect_board( Board ) - reflects Board around horizontal axis
%
%   Transforms a tic-tac-toe board by rotating it 90 degrees
%   clockwise, and by reflecting it around the horizontal axis.
%   Reflecting it is like picking the paper up and putting it
%   face down.
%
%   From these 2 primitive transforms we can construct the 8
%   simple rotation/reflection transforms.

rotate_board(
  {_1,_2,_3,
   _4,_5,_6,
   _7,_8,_9} )
->
  {_7,_4,_1,
   _8,_5,_2,
   _9,_6,_3}.

reflect_board(
  {_1,_2,_3,
   _4,_5,_6,
   _7,_8,_9} )
->
  {_7,_8,_9,
   _4,_5,_6,
   _1,_2,_3}.

% --------------------------------------------------------------
% is_board_won_by( Mark, Board )
%
%   Predicate to test if Board is a winning board for Mark.
%   Returns 'true' or 'false'.
%
%   Board is a 9-tuple.

% Try to speed this up a little.
-compile( {inline,
   [
     is_board_won_all_rows/2,
     is_board_won_all_columns/2,
     is_board_won_rising_diagonal/2,
     is_board_won_falling_diagonal/2,
     is_board_won_upright_Y/2,
     is_board_won_tilt_right_Y/2,
     is_board_won_upside_down_Y/2,
     is_board_won_tilt_left_Y/2,
     is_board_won_upright_4Y/2,
     is_board_won_tilt_right_4Y/2,
     is_board_won_upside_down_4Y/2,
     is_board_won_tilt_left_4Y/2,
     is_board_won_four_corners/2,
     is_board_won_four_sides/2,
     is_board_won_nw_bend/2,
     is_board_won_ne_bend/2,
     is_board_won_sw_bend/2,
     is_board_won_se_bend/2
   ]}).

is_board_won_by( Xo, Board ) ->
  (?c_win_pattern_all_rows                andalso
     is_board_won_all_rows(         Board, Xo)) orelse
  (?c_win_pattern_all_columns             andalso
     is_board_won_all_columns(      Board, Xo)) orelse

  (?c_win_pattern_rising_diagonal         andalso
     is_board_won_rising_diagonal(  Board, Xo)) orelse
  (?c_win_pattern_falling_diagonal        andalso
     is_board_won_falling_diagonal( Board, Xo)) orelse

  (?c_win_pattern_upright_Y               andalso
     is_board_won_upright_Y(        Board, Xo)) orelse
  (?c_win_pattern_tilt_right_Y            andalso
     is_board_won_tilt_right_Y(     Board, Xo)) orelse
  (?c_win_pattern_upside_down_Y           andalso
     is_board_won_upside_down_Y(    Board, Xo)) orelse
  (?c_win_pattern_tilt_left_Y             andalso
     is_board_won_tilt_left_Y(      Board, Xo)) orelse

  (?c_win_pattern_upright_4Y              andalso
     is_board_won_upright_4Y(       Board, Xo)) orelse
  (?c_win_pattern_tilt_right_4Y           andalso
     is_board_won_tilt_right_4Y(    Board, Xo)) orelse
  (?c_win_pattern_upside_down_4Y          andalso
     is_board_won_upside_down_4Y(   Board, Xo)) orelse
  (?c_win_pattern_tilt_left_4Y            andalso
     is_board_won_tilt_left_4Y(     Board, Xo)) orelse

  (?c_win_pattern_four_corners            andalso
     is_board_won_four_corners(     Board, Xo)) orelse
  (?c_win_pattern_four_sides              andalso
     is_board_won_four_sides(       Board, Xo)) orelse

  (?c_win_pattern_nw_bend                 andalso
     is_board_won_nw_bend(          Board, Xo)) orelse
  (?c_win_pattern_ne_bend                 andalso
     is_board_won_ne_bend(          Board, Xo)) orelse
  (?c_win_pattern_sw_bend                 andalso
     is_board_won_sw_bend(          Board, Xo)) orelse
  (?c_win_pattern_se_bend                 andalso
     is_board_won_se_bend(          Board, Xo)).

% --------------------------------------------------------------
% is_board_won_all_rows(         Board, Mark )
% is_board_won_all_columns(      Board, Mark )
% is_board_won_rising_diagonal(  Board, Mark )
% is_board_won_falling_diagonal( Board, Mark )
%
% is_board_won_upright_Y(        Board, Mark )
% is_board_won_tilt_right_Y(     Board, Mark )
% is_board_won_upside_down_Y(    Board, Mark )
% is_board_won_tilt_left_Y(      Board, Mark )
%
% is_board_won_upright_4Y(       Board, Mark )
% is_board_won_tilt_right_4Y(    Board, Mark )
% is_board_won_upside_down_4Y(   Board, Mark )
% is_board_won_tilt_left_4Y(     Board, Mark )
%
% is_board_won_four_corners(     Board, Mark )
% is_board_won_four_sides(       Board, Mark )
%
% is_board_won_nw_bend(          Board, Mark )
% is_board_won_ne_bend(          Board, Mark )
% is_board_won_sw_bend(          Board, Mark )
% is_board_won_se_bend(          Board, Mark )
%
%   All possible winning board patterns, including
%   experimental ones controlled by preprocessor macros.

% ---------------------------
% Check for 3-in-a-row:
is_board_won_all_rows( {X,X,X,
                        _,_,_,
                        _,_,_}, X ) -> true;
is_board_won_all_rows( {_,_,_,
                        X,X,X,
                        _,_,_}, X ) -> true;
is_board_won_all_rows( {_,_,_,
                        _,_,_,
                        X,X,X}, X ) -> true;
is_board_won_all_rows( _      , _ ) -> false.

% ---------------------------
% Check for 3-in-a-column:
is_board_won_all_columns( {X,_,_,
                           X,_,_,
                           X,_,_}, X ) -> true;
is_board_won_all_columns( {_,X,_,
                           _,X,_,
                           _,X,_}, X ) -> true;
is_board_won_all_columns( {_,_,X,
                           _,_,X,
                           _,_,X}, X ) -> true;
is_board_won_all_columns( _      , _ ) -> false.

% ---------------------------
% Check the diagonals.
is_board_won_rising_diagonal(  {_,_,X,
                                _,X,_,
                                X,_,_}, X ) -> true;
is_board_won_rising_diagonal(  _      , _ ) -> false.

is_board_won_falling_diagonal( {X,_,_,
                                _,X,_,
                                _,_,X}, X ) -> true;
is_board_won_falling_diagonal( _      , _ ) -> false.

% ---------------------------
% Check the Y's
is_board_won_upright_Y(     {X,_,X,
                             _,_,_,
                             _,X,_}, X ) -> true;
is_board_won_upright_Y(     _      , _ ) -> false.

is_board_won_tilt_right_Y(  {_,_,X,
                             X,_,_,
                             _,_,X}, X ) -> true;
is_board_won_tilt_right_Y(  _      , _ ) -> false.

is_board_won_upside_down_Y( {_,X,_,
                             _,_,_,
                             X,_,X}, X ) -> true;
is_board_won_upside_down_Y( _      , _ ) -> false.

is_board_won_tilt_left_Y(   {X,_,_,
                             _,_,X,
                             X,_,_}, X ) -> true;
is_board_won_tilt_left_Y(   _      , _ ) -> false.

% ---------------------------
% Check the 4Y's
is_board_won_upright_4Y(     {X,_,X,
                              _,X,_,
                              _,X,_}, X ) -> true;
is_board_won_upright_4Y(     _      , _ ) -> false.

is_board_won_tilt_right_4Y(  {_,_,X,
                              X,X,_,
                              _,_,X}, X ) -> true;
is_board_won_tilt_right_4Y(  _      , _ ) -> false.

is_board_won_upside_down_4Y( {_,X,_,
                              _,X,_,
                              X,_,X}, X ) -> true;
is_board_won_upside_down_4Y( _      , _ ) -> false.

is_board_won_tilt_left_4Y(   {X,_,_,
                              _,X,X,
                              X,_,_}, X ) -> true;
is_board_won_tilt_left_4Y(   _      , _ ) -> false.

% ---------------------------
% Check corners - 4-mark pattern
is_board_won_four_corners( {X,_,X,
                            _,_,_,
                            X,_,X}, X ) -> true;
is_board_won_four_corners( _      , _ ) -> false.

% ---------------------------
% Check sides - 4-mark pattern
is_board_won_four_sides( {_,X,_,
                          X,_,X,
                          _,X,_}, X ) -> true;
is_board_won_four_sides( _      , _ ) -> false.

% ---------------------------
% Check the corner bends
is_board_won_nw_bend( {X,X,_,
                       X,_,_,
                       _,_,_}, X ) -> true;
is_board_won_nw_bend( _      , _ ) -> false.

is_board_won_ne_bend( {_,X,X,
                       _,_,X,
                       _,_,_}, X ) -> true;
is_board_won_ne_bend( _      , _ ) -> false.

is_board_won_sw_bend( {_,_,_,
                       X,_,_,
                       X,X,_}, X ) -> true;
is_board_won_sw_bend( _      , _ ) -> false.

is_board_won_se_bend( {_,_,_,
                       _,_,X,
                       _,X,X}, X ) -> true;
is_board_won_se_bend( _      , _ ) -> false.


% --------------------------------------------------------------
% report_board( Board, Board_props )
%
%   We could pass in the current and next ply are report
%   predictions for all the next moves:
%
%     XXX
%     .O. X wins
%     O..
%
%     XX.    XXO         XX.
%     .O. -> .O. O wins  OO. X will win (in 1 or 3 moves)
%     O.X    O.X         O.X
%
%   We could even report on all predictions from here.
%   For each next_board:
%     X will win: 10 paths
%       3 moves: 9 paths
%       2 moves: 1 path
%       1 move:  0 paths
%     Tie: 13 paths
%     Lose: 3 paths
%       3 moves: 9 paths
%
%   Maybe we should have a report_move(..) function that
%   reports on a source board and move. Usually we want to
%   know about all the next moves.

report_board( {_1,_2,_3,_4,_5,_6,_7,_8,_9}, Board_props ) ->
  State       = get_board_props_state( Board_props),
  Next_boards = get_board_props_next_boards( Board_props),
  Write_mark  = fun( M ) ->
    write_string(
      if
        M =:= ?EMPTY -> ".";
        true         -> get_mark_string( M)
      end)
  end,
  Write_strip = fun( A, B, C ) ->
    Write_mark( A),
    Write_mark( B),
    Write_mark( C)
  end,

  write_space( 4),
  Write_strip( _1, _2, _3),
  case State of
    continuing ->
      write_string( "    "),
      filter_next_boards(
        fun( {__1,__2,__3,_,_,_,_,_,_} ) ->
          Write_strip( __1, __2, __3),
          write_space( 2),
          false
        end,
        Next_boards);
    _ -> ok
  end,
  write_line( ),

  write_space( 4),
  Write_strip( _4, _5, _6),
  case State of
    win -> write_string( " winner");
    tie -> write_string( " tie");
    continuing ->
      write_string( " -> "),
      filter_next_boards(
        fun( {_,_,_,__4,__5,__6,_,_,_} ) ->
          Write_strip( __4, __5, __6),
          write_space( 2),
          false
        end,
        Next_boards)
  end,
  write_line( ),

  write_space( 4),
  Write_strip( _7, _8, _9),
  case State of
    continuing ->
      write_string( "    "),
      filter_next_boards(
        fun( {_,_,_,_,_,_,__7,__8,__9} ) ->
          Write_strip( __7, __8, __9),
          write_space( 2),
          false
        end,
        Next_boards);
    _ -> ok
  end,
  write_line( ).


% --------------------------------------------------------------
% Simple String Output
% --------------------------------------------------------------

% --------------------------------------------------------------
% write_line( )
% write_line( Str, Arg)
% write_line( Str, A1, A2)
% write_line( Str, A1, A2, A3)
% write_line( Str, A1, A2, A3, A4)
% write_string( Str)
% write_string( Str, Arg)
% write_string( Str, A1, A2)
% write_string( Str, A1, A2, A3)
% write_string( Str, A1, A2, A3, A4)
% write_space( )
% write_space( N)

write_line( ) ->
  io:nl( ).

write_line( Str ) ->
  write_string( Str),
  write_line( ).

write_line( Str, Arg ) ->
  write_string( Str, Arg),
  write_line( ).

write_line( Str, A1, A2 ) ->
  write_string( Str, A1, A2),
  write_line( ).

write_line( Str, A1, A2, A3 ) ->
  write_string( Str, A1, A2, A3),
  write_line( ).

write_line( Str, A1, A2, A3, A4 ) ->
  write_string( Str, A1, A2, A3, A4),
  write_line( ).

write_string( Str ) ->
  io:fwrite( Str).

write_string( Str, Arg ) ->
  io:fwrite( Str, [Arg]).

write_string( Str, A1, A2 ) ->
  io:fwrite( Str, [A1, A2]).

write_string( Str, A1, A2, A3 ) ->
  io:fwrite( Str, [A1, A2, A3]).

write_string( Str, A1, A2, A3, A4 ) ->
  io:fwrite( Str, [A1, A2, A3, A4]).

write_space( ) ->
  write_string( " ").

write_space( 0 ) ->
  ok;
write_space( N ) when N > 0 ->
  write_space( ),
  write_space( N - 1).
